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