Python Solution with Detailed Explanation


  • 0
    G

    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
    

Log in to reply
 

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