459 Repeated Substring Pattern

1. Description

Given a string s, check if can be constructed by taking a substring of it and appending multiple copies of the substring together.

 

constraints :

• 1 <= s.length <= \(10^{4}\)
• s consists of lowercase English letters.

2. Algorithms

If there is any repeated substring pattern in input string s, the length of pattern is divisor of full length of input strings. The biggest substring in pattern can be half length of total length.

 

For example, let's talk about when input string s is "abcabcabc". If substring is "a", then "a" * 9 (len(s) / len(substring)) should be same.

 

1. Start
2. Declare variable substring and initialize as empty string.
3. Repeat steps through range 0 to half of input string.
   1. Append corresponding character to substring.
   2. If length of substring can be divided by length of input s and result of substring multiply (len(s) / len(substring)) is same with input s, return True.
4. Return False out of loop.
5. End

3. Codes

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
    	# substring : stores substring to check if current substring is repeated substring
        substring = "" 
        
        for i in range(len(s) // 2) : 
            substring += s[i]
            # Check if current substring is repeated substring.
            if (len(s) % len(substring) == 0) and (substring * (len(s) // len(substring)) == s) : 
                return True 
        return False

4. Conclusion