Problem: 459. 重复的子字符串
思路
给定一个非空的字符串 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的长度。
空间复杂度:文章来源:https://www.toymoban.com/news/detail-826511.html
该算法的时间复杂度为O(n^2),空间复杂度为O(1)。文章来源地址https://www.toymoban.com/news/detail-826511.html
代码
class Solution(object):
def repeatedSubstringPattern(self, s):
n = len(s)
for i in range(1,n//2+1):
if n%i == 0:
sub_str=s[:i]
if sub_str * (n//i) == s:
return True
return False
到了这里,关于力扣代码学习日记四的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!