LeetCode 23.字符串的最大公因子 辗转相除法

题目描述

对于字符串 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] 为大写英文字母

 

解题思路

看到标题里面有最大公因子这个词,于是先默写一下 gcd 算法

private int gcd(int a, int b) {
        return b == 0? a: gcd(b, a % b);
    }

总有一种好像顺手就能用上的感觉呢。

其实看起来两个字符串之间能有这种神奇的关系是挺不容易的,我们希望能够找到一个简单的办法识别是否有解。

如果它们有公因子 abc,那么 str1 就是 mm 个 abc 的重复,str2 是 nn 个 abc 的重复,连起来就是 m+nm+n 个 abc,好像 m+nm+n 个 abc 跟 n+mn+m 个 abc 是一样的。

所以如果 str1 + str2 == str2 + str1 就意味着有解。

我们也很容易想到 str1 + str2 != str2 + str1 也是无解的充要条件。

当确定有解的情况下,最优解是长度为 gcd(str1.length, str2.length) 的字符串。

这个理论最优长度是不是每次都能达到呢?是的。

因为如果能循环以它的约数为长度的字符串,自然也能够循环以它为长度的字符串,所以这个理论长度就是我们要找的最优解。

把刚刚写的那些拼起来就是解法了。

代码如下

class Solution {
   public String gcdOfStrings(String str1, String str2) {
        // 假设str1是N个x,str2是M个x,那么str1+str2肯定是等于str2+str1的。
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        // 辗转相除法求gcd。
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    private int gcd(int a, int b) {
        return b == 0? a: gcd(b, a % b);
    }
}

 

 

 

原文地址:https://www.cnblogs.com/Transkai/p/12468142.html