LeetCode 1071. 字符串的最大公因子（python）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 1071. 字符串的最大公因子（python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1756字，纯文字阅读大概需要3分钟。
内容图文
题目描述：
对于字符串 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”
输出：""
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
解题思路：
采用二重循环
首先判断当前字符串是不是公共前缀（如A,AB,ABC）
若是公共前缀，则在分别判断该字符串能否循环组成str1和str2
这种方法时间比较长
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
res=''
i=0
while i<min(len(str1),len(str2)):
x=str1[:i+1]
if str1[:i+1]!=str2[:i+1]:
break
else:
rr=x
flag1,flag2=0,0
while len(rr)<=len(str1):
if rr==str1:
flag1=1
rr+=x
rr=x
while len(rr)<=len(str2):
if rr==str2:
flag2=1
rr+=x
if flag1==1 and flag2==1:
res=x
i+=1
return res
评论区答案：
执行时间32ms
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if len(str1) < len(str2):
str1, str2 = str2, str1#将短的字符串赋给str2
len_str1 = m = len(str1)
len_str2 = n = len(str2)
res = ''
while n > 0:
m, n = n, m%n#辗转相除法求最大公因子
gcd = m
rep1, rep2 = str1[:gcd], str2[:gcd]
#判断最大公因子对应的前缀是否相等，以及是否能构成字符串str1和str2
if rep1 == rep2 and str1 == len_str1//gcd *rep1 and str2 == len_str2//gcd*rep2:
return rep1
return res
评论区方法2：
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
sort_str = lambda s1, s2: (s2, s1) if len(s2) > len(s1) else (s1, s2)
long, short = sort_str(str1, str2)#长的赋给long，短的赋给short
while long != short:
if short not in long:
return ''
long = long.replace(short, '', 1)#将长的中的短的删除
long, short = sort_str(short, long)
return short
内容总结
以上是互联网集市为您收集整理的LeetCode 1071. 字符串的最大公因子（python）全部内容，希望文章能够帮你解决LeetCode 1071. 字符串的最大公因子（python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。