百度外卖网站建设与维护方法,wordpress register位置,软件商城有哪些,网推app下载Problem: 459. 重复的子字符串 文章目录 思路解题方法复杂度代码 思路 给定一个非空的字符串 s #xff0c;检查是否可以通过由它的一个子串重复多次构成。 示例 1:
输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2:
输入: s 检查是否可以通过由它的一个子串重复多次构成。 示例 1:
输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2:
输入: s aba
输出: false示例 3:
输入: s abcabcabcabc
输出: true
解释: 可由子串 abc 重复四次构成。 (或子串 abcabc 重复两次构成。)提示
1 s.length 104
s 由小写英文字母组成解题方法 可以考虑将原始字符串看作是由其最小循环节组成的。如果存在一个子串将这个子串重复多次后可以得到原始字符串则原始字符串可以由这个子串重复构成。 复杂度
时间复杂度: 时间复杂度为O(n * n//2)即O(n^2)其中n是字符串s的长度。 空间复杂度: 该算法的时间复杂度为O(n^2)空间复杂度为O(1)。 代码
class Solution(object):def repeatedSubstringPattern(self, s):n len(s)for i in range(1,n//21):if n%i 0:sub_strs[:i]if sub_str * (n//i) s:return Truereturn False
