[459][简单] 重复的子字符串

题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

解题思路

直接的思路是遍历所有可能的pattern长度, 从1遍历到n//2.

但有一个便捷的思路. 如果字符串s是由另一个子串重复得到, 则s中至少包含两个对应的子串, 则将两个s拼接在一起组成的更长的字符串中, 至少包含4个对应的子串.

这样我们头尾各去掉一个字符, 破坏了两个子串结构, 但中间的部分肯定还报单一个完整的原始的s, 否则s是非重复的.

代码如下:

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s and s in (s + s)[1:-1]