题目描述
对于字符串 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 = "LEET", str2 = "CODE"
输出：""
解答方法
方法一：数学法
思路
先判断 str1 和 str2 拼接后是否等于 str2 和 str1 拼接起来的字符串，如果等于直接输出长度为 gcd(len 1,len 2) 的前缀串即可，否则返回空串。
代码
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 == str2 + str1:
return str1[:math.gcd(len(str1),len(str2))]
return ''
时间复杂度
O(n) ，字符串拼接比较是否相等需要 O(n) 的时间复杂度，求两个字符串长度的最大公约数需要 O(logn) 的时间复杂度，所以总时间复杂度为O(n+logn)=O(n) 。
空间复杂度
O(n) ，程序运行时建立了中间变量用来存储 str1 与 str2 的相加结果。
