[Leetcode]459. Repeated Substring Pattern

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.

Brute force

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

Optimized

@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 in ss[1...n-1].

Imaging s is formed by repeated substrings such as aa – by at least two repeated substrings.. Then ss is aaaa. When we take ss[1...n-1], the first and last repeated substrings are destroyed so it becomes baab.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        ss = (s+s)[1:-1]
        return ss.find(s)!=-1

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments