Leetcode: Repeated substring pattern
The task is to find out if a given string is comprised of multiple identical substrings. The first observation is that the substring cannot be longer than half of the length of the original string. The second observation is that the length of the total string has to be a multiple of the string that is tested, if it is not it can be discarded right away. Lastly, a string with the length of one can be discarded immediately.
The main idea is to try out every string from size 1 to n/2+1 and break immediately of the next character is not the expected one. As an additional optimization, substrings whose length do not fit into the whole string can be discarded immediately.
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
for length in range(1, int(len(s)/2)+1):
# Discard strings with invalid length
if len(s)%length != 0:
continue
ok = True
# Create substring to test
curr = s[:length]
for char in range(length, len(s)):
# Test character of substring.
# Only continue if character is as expected.
if s[char] != curr[char%length]:
ok = False
break
if ok:
return True
# No valid substring found
return False
if __name__ == '__main__':
r = Solution().repeatedSubstringPattern
print(r("aabaaba"), False)
print(r("abcabc"), True)
print(r("ababab"), True)
print(r('abcxyz'), False)
print(r('a'), False)