字符串的最大公因子：
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
示例 3：
输入：str1 = "ABABABAB", str2 = "ABAB"
输出："ABAB"
示例 4：
输入：str1 = "LEET", str2 = "CODE"
输出：""
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
自我解答：
呃，自己尝试的方法是双指针，写的又长又臭，调了半天发现题意理解有偏差，写成求字符串最小公因子。。
于是直接看答案了。
力扣题解：
方法一：和求最大公约数一样，可以使用 “辗转相除法”
引用网友的一句话“对不起我不配活在2020我应该活在公元前301年前”。
自己实现的“辗转相除”：
1、可以使用双指针，模拟一个一个找公共字符的过程，如果有不一样的字符，则说明无解，
若一样，记录下公共字符，当某个字符串到达末尾后，结束
2、拿到公共字符串，和剩下的字符串再进行 1 操作，直到str1和str2 都没有剩余字符串了，
得到最大公共字符串。
def gcd_of_strings(str1: str, str2: str) -> str:
str1_len = len(str1)
str2_len = len(str2)
commons = []
i = 0
j = 0
while i < str1_len and j < str2_len:
if str1[i] != str2[j]:
return ""
else:
commons.append(str1[i])
i += 1
j += 1
if i < str1_len:
return gcd_of_strings("".join(commons), str1[i:str1_len])
if j < str2_len:
return gcd_of_strings("".join(commons), str2[j:str2_len])
return "".join(commons)
力扣题解：
1、假设存在这个公共字符串，那么这两个字符串应该存在关系：str1 + str2 == str2 + str1，
可以直接用这个代替"双指针判断是否有不一样的字符"操作，
2、另外，这两个字符串必然是包含关系，在满足1的前提下，更短的那个字符串就是一个公共字符串，
由此，便可以代替双指针记录公共字符串的功能。
3、拿到公共字符串再和剩下的字符串进行 2 操作，直到 2操作中对比的两个字符串相等为止。
def gcd_of_string2(str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ""
len1, len2 = len(str1), len(str2)
if len1 == len2:
return str1
elif len1 > len2:
return gcd_of_string2(str2, str1[len2:])
else:
return gcd_of_string2(str1, str2[len1:])
还有可特别秀的版本
def gcd_of_string3(str1: str, str2: str) -> str:
import math
return str1[: math.gcd(len(str1), len(str2))] if str1 + str2 == str2 + str1 else ""
原题链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings