[LeetCode] (459) Repeated Substring Pattern

Basic Idea: try to obtain the original string using all possible repeated substring from the shortest to the longest.

class Solution(object):
    def repeatedSubstringPattern(self, str):
        """
        :type str: str
        :rtype: bool
        """
        for i in range(1, len(str) / 2 + 1):
            if len(str) % i == 0 and len(str) / i * str[:i] == str:
                return True
        return False

Time Complexity is O(n^2)

Related posts