[LeetCode] (459) Repeated Substring Pattern

基本思路:从小到大尝试所有可能的子串是否能拼成原始字符串。

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

复杂度为 O(n^2)

Related posts