LeetCode 字符串的最大公因子
程序员文章站
2022-07-15 18:32:40
...
题目描述
对于字符串 S 和 T,只有在 S = T + … + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。
返回最长字符串 X,要求满足 X 能除尽 str1 且 X 能除尽 str2。
分析:
由题目可以看出,这是个变相求最大公因数的题目。只要我们加一个判断条件: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);
}
}
下一篇: Java实现矩阵相乘
推荐阅读
-
js最实用string(字符串)类型的使用及截取与拼接详解
-
js操作如何去掉字符串最外层的双引号,使其变成数组
-
LeetCode 151. 翻转字符串里的单词(java代码和思路分析,模拟题)
-
世界上最危险的九大公路,其中一条是中国最危险的公路
-
LeetCode的一道题引申的python实现的对字符串进行分词,提取词频的方法
-
Python Leetcode 字符串中的第一个唯一字符
-
Leetcode刷题记录——面试题48. 最长不含重复字符的子字符串
-
LeetCode 字符串的最大公因子
-
Leetcode 剑指 Offer 48. 最长不含重复字符的子字符串
-
LeetCode 459. 重复的子字符串 | Python