1. 代码段小站首页
  2. 算法

leetcode1071-字符串的最大公因子

彭晨涛 • • 算法 • 阅读 20

原题

对于字符串 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/

赞 (1)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年3月11日 23:40
下一篇 2020年3月12日 16:38

相关推荐

发表回复

登录后才能评论