0459：重复的子字符串

2016-04-03 约 294 字预计阅读 1 分钟次阅读

力扣第 459 题

题目

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 10⁴
s 由小写英文字母组成

分析

#1

假如长为 n 的 s 能由长 m 的子串 sub 组成，显然 n 是 m 的倍数
因此考虑遍历 n 的因数 m，判断 s 是否由 s[:m] 重复构成即可

1
2
3
4
5
6
7
8
9


class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1,isqrt(n)+1):
            if n%i==0:
                for j in [i,n//i]:
                    if j<n and s[:j]*(n//j)==s:
                        return True
        return False

时间复杂度 $O(N*\sqrt N)$，39 ms

#2

还有个经典的方法，s 由子串 sub 重复组成等价于 s 是 s[1:]+s[:-1] 的子串。

解答

1
2
3


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

42 ms

目录

0459：重复的子字符串

题目

分析

#1

#2

解答