长大后想做什么？做回小孩！

0%

LeetCode——字符串的最大公因子

发表于 更新于 分类于 Valine：
本文字数： 387

NO.1071 字符串的最大公因子 简单

8Z46zj.png

思路一：辗转相除

提示很重要:1<=length

如果两个字符串存在最大公因子X，那么str1就是m个X连接组成的，同样str2就是n个X连接组成的。

即m+n=n+m是两个字符串存在最大公因子的充要条件。

如果确定两个字符串存在最大公因子，就知道两个字符串分别是m或n个X连接组成的。只需要求出两个字符串长度之间的最大公约数即可。

求最大公约数自然是用辗转相除法(欧几里得算法)，具体做法就是： 用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。举例：

8Zq7se.png

1
2
3
4
5
6
7
8
9
10
11
public String gcdOfStrings(String str1, String str2) {
    //判断是否存在最大公因子
    if (!(str1+str2).equals(str2+str1))return "";
    //求最大公因子长度
    int maxLen=GCD(str1.length(),str2.length());
    return str1.substring(0,maxLen);
}
//求辗转相除法求最大公约数
private int GCD(int a, int b) {
    return b==0?a:GCD(b,a%b);
}

时间复杂度:O(n) 字符串拼接后比较O(n),辗转相除法O(logn)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github