leetcode1071-字符串的最大公因子

原题

对于字符串 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. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i] 和 str2[i] 为大写英文字母

解法

思想

这道题我之前想得很复杂!结果一看题解:卧槽还能这样。给大佬们跪了。

确实好久没接触这样的数学知识了:辗转相除法。

首先如果str1和str2有最大公因子,那么str1+str2就会等于str2+str1。

然后就是考虑怎么把最大公因子子字符串取出来,说实话辗转相除法我是没想到的,百度百科:

欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

这样求出两个字符串的长度的最大公因数,就是子字符串的长度,然后用substring取出来。

代码

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 x,int y){
        return x%y==0?y:gcd(y,x%y);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1071-%e5%ad%97%e7%ac%a6%e4%b8%b2%e7%9a%84%e6%9c%80%e5%a4%a7%e5%85%ac%e5%9b%a0%e5%ad%90/

发表回复

登录后才能评论