力扣---1071. 字符串的最大公因子-526互联

对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回最长字符串 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, str2.length <= 1000
str1 和 str2 由大写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/greatest-common-divisor-of-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

很好奇为啥这题被标为简单，可能是因为直接暴力法可以通过？

辗转相除法：

首先可以确定的是：如果 str1 和 str2 有公共子字符串，那么 str1 + str2 必定与 str2 + str1 相同。

可以假设 str1 为 n 个 x，str2 为 m 个 x。

那么，str1 + str2 就等于（m + n）个 x，与 str2 + str1 相同。

通过这一点可以先判断是否有公共子字符串。

判断后，如果有子字符串，那么假设最大公共子字符串为 str3，那么，str1 == m 个 str3，str2 == n 个 str3。

可以想到，这其实就是求 str1.length() 和 str2.length() 的最大公约数。

对比如下：

设 x 和 y 的最大公约数为 z。

那么，x = n * z；y = m * z；

设 str1 和 str2 的最长公共子字符串为 str3，那么，str1 = n * str3；str2 = m * str3；

于是，可以想到利用辗转相除法来求最大公约数。

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);
    }
}