原题
对于字符串 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] 为大写英文字母
解法
思想
这道题我之前想得很复杂!结果一看题解:卧槽还能这样。给大佬们跪了。
确实好久没接触这样的数学知识了:辗转相除法。
首先如果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/