# Python Solution with Detailed Explanation

• Solution

Repeated Substring Pattern https://leetcode.com/problems/repeated-substring-pattern/

Optimized Brute Force

• Length of the substring, say sl, can vary from N//2 to 1
• sl should be a divisor of N
• Given an sl (i.e. length of a substring), we can simply compare it to all consecutive substrings of length sl within original s. We return False at any mismatch.
• What is the time complexity of this algorithm?
• The outer loop runs N//2 times. The inner loop makes at-most character comparisons. So the time complexity (using character comparison) will be N^2.
• Lets say we characterize string comparison as a unit of comparison. Then the time complexity will N * M will M will be the maximum iterations of inner loop. Now M = N//i. So M is bounded by sqrt(N) since when N = a * b and the smaller divisor is bounded by sqrt(N). And in this case, M is always the smaller divisor since we start i with N//2.
• Refer to this link for more details: https://discuss.leetcode.com/topic/67992/java-simple-solution-with-explanation/10
class Solution(object):
def test(self, i, s):
pattern = s[0:i]
# How many iterations m does this loop have? m = N//i
# Now m is bounded by sqrt(N) since N = a * b and the smaller divisor is bounded by sqrt(N)
# In this case m is always the smaller divisor since we start i with N//2
for j in range(i, len(s)-i + 1,i):
match = s[j:j+i]
if pattern != match:
return False
return True

def repeatedSubstringPattern(self, s):
"""
:type str: str
:rtype: bool
"""
N = len(s)
for i in range(N//2, 0, -1):
if N%i == 0:
if self.test(i, s):
return True
return False

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.