LeetCode 459 - 重复的子字符串

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        # 求所有因数的方法
        def get_factors(n):
            factors = set()
            # 只需要遍历从1到n ** 0.5，每找到一个因数i，就能通过n // i求出另一个因数
            for i in range(1, int(n ** 0.5) + 1):
                if n % i == 0:
                    factors.add(i)
                    factors.add(n // i)
            return sorted(factors)
        factors = get_factors(len(s))
        # 抛弃数组长度，也就是最后一个值
        factors = factors[0:len(factors) - 1]

        # 按照每个因数分段比对
        def repeatedSubstringPatternIMPL(s: str, n: int):
            sSub = s[0:n]
            i = n
            while i < len(s):
                if sSub != s[i:i + n]:
                    return False
                else:
                    i += n
            return True

        # 只要有一个因数能做到就提前剪枝结束
        for i in range(len(factors) - 1, -1, -1):
            if repeatedSubstringPatternIMPL(s, factors[i]) == True:
                return True
        return False