Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
If it can be composed by repeated strings
sub, then the length of
sub could be at most
len(s)/2 and at least
1. So we can iterate through all possibles lengths and for each length, check whether we can construct the entire string by appending the repeated ones.
class Solution: def repeatedSubstringPattern(self, s: str) -> bool: n = len(s) for i in range(2,n+1): # divide s into i parts if n%i==0: l = n//i # the length of the repeated string flag = True for j in range(i-1): if s[j*l:(j+1)*l] != s[(j+1)*l:(j+2)*l]: flag = False break if flag: return True return False
@rsrs3 provides a smarter way to deal with this problem. Given the string
s, we append another
s to it and now we have
ss. Then all we need to do is to find
s is formed by repeated substrings such as
aa – by at least two repeated substrings.. Then
aaaa. When we take
ss[1...n-1], the first and last repeated substrings are destroyed so it becomes
class Solution: def repeatedSubstringPattern(self, s: str) -> bool: ss = (s+s)[1:-1] return ss.find(s)!=-1