欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 字符串的最大公因子

程序员文章站 2022-07-15 18:32:40
...

题目描述
对于字符串 S 和 T,只有在 S = T + … + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。

返回最长字符串 X,要求满足 X 能除尽 str1 且 X 能除尽 str2。
LeetCode 字符串的最大公因子分析:
由题目可以看出,这是个变相求最大公因数的题目。只要我们加一个判断条件:str1+str2=str2+str1。两个字符串如果有最大公因数,则他们交换位置相加和交换位置之前相加的结果相同。求最大公约数(GCD),这里用的是辗转相除法,两个数的最大公因数等于除数和余数的公约数。gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)。当余数为零时,除数就是最大公因数。

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if(!(str1+str2).equals(str2+str1)){
            return "";
        }
        return str1.substring(0,gcd(str1.length(),str2.length()));
    }
    public int gcd(int a,int b){
        if(b==0)
        return a;
        int c = a%b;
        return gcd(b,c);
    }
}
相关标签: LeetCode刷题总结