1071.字符串的最大公因子

解题思路

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数(Greatest Common Divisor)缩写为GCD。
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

gcd(a,b) = b if a%b == 0 else gcd(b,a%b)
或者
gcd(a,b) = a if b==0 else gcd(b,a%b)

注意到一个性质：如果存在一个符合要求的字符串 X，那么也一定存在一个符合要求的字符串 X'，它的长度为 str1 和 str2 长度的最大公约数。

简单来说，我们已经知道符合条件的长度出现在 gcd(len_1, len_2)的所有约数中，我们假设其中一个满足条件的约数为x，该长度为 len_x的前缀串 X 能经过若干次拼接后得到 str1 和 str2。拿 str1 举例，X 经过 len_1/len_x 次拼接后得到了 str1，而 X 又能经过 gcd(len_1, len_2)/len_x 次拼接后得到长度为 gcd(len_1,len_2)的前缀串 X'，所以我们可以每次取出 gcd(len_1, len_2)/len_x 个 X 来用 X'完成替换，最后 str1 会被替换成 len_1/gcd(len_1,len_2) 个 X'，str2 同理可得。因此如果存在一个符合要求的字符串 X，那么也一定存在一个符合要求的字符串 X'，它的长度为 str1 和 str2 长度的最大公约数。我们只需要判断长度为 gcd(len_1,len_2)的前缀串是否满足要求即可。

算法
由上述性质我们可以先用辗转相除法求得两个字符串长度的最大公约数 gcd(len_1,len_2)，取出该长度的前缀串，判断一下它是否能经过若干次拼接得到 str1 和 str2 即可。

复杂度分析：
时间复杂度：O(n)，其中 n 是两个字符串的长度范围，即 len_1 + len_2 。判断最大公约数长度的前缀串是否符合条件需要 O(n) 的时间复杂度，求两个字符串长度的最大公约数需要 )O(logn) 的时间复杂度，所以总时间复杂度为 O(n+logn)=O(n)。
空间复杂度：O(n)，比较的过程中需要创建一个长度创建长度为 O(n) 的临时字符串变量，所以需要额外 O(n) 的空间。

代码

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        if m < n:
            return self.gcdOfStrings(str2, str1)
        def gcd(a,b):
            return b if a%b==0 else gcd(b, a%b)
        r = gcd(m, n)
        if (str1[:r] == str2[:r] and str1[:r]*(len(str1)//r) == str1 and str2[:r]*(len(str2)//r) == str2):
            return str1[:r]
        return ""