LeetCode 1071. Greatest Common Divisor of Strings

For strings S and T, we say "T divides S" if and only if S = T + ... + T  (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Note:

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.

思路：

根据题意，如果str2是str1的若干个组成，那必然存在str1 + str2 == str2 + str1，反之亦然，即如果str1 + str2 ！= str2 + str1，那么这两个字符串一定不存在公因式。

又因为找最大公因子，所以可以从最大开始遍历，两个字符串都会是最大公因子的整数个组成，即gcd_str * n1 == str1 and gcd_str * n2 == str2; 其中n1表示多少个公因子组成str1，n2表示多少个公因子组成str2

class Solution:
 
    def gcdOfStrings(self, str1: str, str2: str) -> str:
 
        if str1 + str2 != str2 + str1:
 
            return ""
 
 
 
        size1 = len(str1)
 
        size2 = len(str2)
 
 
 
        for i in range(min(size1, size2), 0, -1):
 
            if size1 % i == 0 and size2 % i == 0:
 
                if str1[:i] * (size1 // i) == str1 and str1[:i] * (size2 // i) == str2:
 
                    return str1[:i]
 
        return ""