Leetcode-1071-GCD-of-Strings

🧠 思路总结

1. 题目本质是在找一个最短重复单元，使它能重复拼接得到 str1 和 str2。
2. 如果两个字符串来自同一个重复单元，那么 str1 + str2 和 str2 + str1 的结果一定完全相同。
3. 在确认结构一致后，问题就转化为：这个重复单元的长度是多少(最大公约数（GCD）)。

❗ 易错点 / 小坑

1. 最大公约字符串一定是前缀，不需要考虑中间子串
2. gcd 方法本质是欧几里得算法，递归结束条件是 b == 0

✅ 代码（Java）

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
             return "";
        }
        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }

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