力扣-1071.字符串的最大公约数【Python】

LeetCode1071.字符串的最大公约数【易】【Python】【字符串】问题LeetCode对于字符串S和T，我们说“T整除S”当且仅当S=T+...+T（T与自身连接1次或多次）返回最大的字符串X，使X整除str1，X整除str2。示例1：输入：str1="ABCABC",str2="ABC"输出："ABC"示例2：输入：str1="ABABAB",str2="ABAB"输出："AB"示例3：输入：str1="LEET",str2="CODE"Output:""注：1<=str1.length<=10001<=str2.length<=1000str1[i]和str2[i]为英文大写字母。问题在于，对于字符串S和T，只有当S=T+...+T时（T与自身相连一次或多次），我们才认为“T可以完全整除S”。返回最长的字符串X，使得X可以整除str1并且X可以整除str2。示例1：输入：str1="ABCABC",str2="ABC"输出："ABC"示例2：输入：str1="ABABAB",str2="ABAB"输出："AB"示例3：输入：str1="LEET",str2="CODE"输出：""提示：1<=str1.length<=10001<=str2.length<=1000str1[i]和str2[i]为大写英文字母。str2逐个比较字符，不相等则返回""。如果相等，则找出m和n的最大公约数，返回str1中从头到最大公约数位置的字符串。（左闭右开）时间复杂度：O(max(m,n))，m为str1的长度，n为str2的长度。空间复杂度：O(log(min(m,n)))，m为str1的长度，n为str2的长度。Python3代码类解决方案：defgcdOfStrings(self,str1:str,str2:str)->str:m,n=len(str1),len(str2)#解决方案一i,j=0,0whileistr:m,n=len(str1),len(str2)#解决方案二ifstr1+str2!=str2+str1:return""#求最大公约数defgcd(a,b):returnaifb==0elsegcd(b,a%b)returnstr1[:gcd(m,n)]if__name__=="__main__":str1="ABCABC"str2="ABC"print(Solution().gcdOfStrings(str1,str2))代码地址GitHub链接