1071.字符串的最大公因子

题目

对于字符串 s 和 t，只有在 s = t + t + t + … + 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 由大写英文字母组成

---

解题思路

问题理解

我们需要找到两个字符串 str1 和 str2 的最大公因子字符串 x。这里的最大公因子字符串 x 需要满足以下条件：

1. x 能够通过重复多次拼接得到 str1。
2. x 能够通过重复多次拼接得到 str2。
3. x 是所有满足上述条件的字符串中最长的那个。
   换句话说，x 是能够同时“除尽” str1 和 str2 的最长字符串。

关键观察

1. 字符串长度的关系：
   • 如果存在这样的 x，那么 x 的长度必须是 str1 长度和 str2 长度的公约数。因为：
     • str1 可以看作是 x 重复 len(str1)/len(x) 次。
     • str2 可以看作是 x 重复 len(str2)/len(x) 次。
   • 因此，len(x) 必须是 len(str1) 和 len(str2) 的最大公约数（GCD）。
2. 字符串拼接验证：
   • 为了确保 x 确实能够同时除尽 str1 和 str2，我们需要验证 str1 + str2 是否等于 str2 + str1。
   • 如果 str1 + str2 == str2 + str1，说明 str1 和 str2 都是由同一个基本字符串 x 重复不同次数构成的。
   • 如果 str1 + str2 != str2 + str1，说明不存在这样的 x，直接返回空字符串 “”。

算法步骤

1. 检查拼接是否相等：
   • 计算 str1 + str2 和 str2 + str1，并比较它们是否相等。
   • 如果不相等，返回 “”。
2. 计算长度的最大公约数（GCD）：
   • 使用辗转相除法（欧几里得算法）计算 len(str1) 和 len(str2) 的 GCD。
3. 提取最大公因子字符串：
   • 从 str1 或 str2 的前 GCD 个字符中提取子串，作为结果返回。

示例验证

示例 1：

• str1 = “ABCABC”, str2 = “ABC”
  • str1 + str2 = “ABCABCABC”, str2 + str1 = “ABCABCABC” → 相等。
  • len(str1) = 6, len(str2) = 3, GCD(6, 3) = 3。
  • 返回 str1.substring(0, 3) = “ABC”。
    示例 2：
• str1 = “ABABAB”, str2 = “ABAB”
  • str1 + str2 = “ABABABABAB”, str2 + str1 = “ABABABABAB” → 相等。
  • len(str1) = 6, len(str2) = 4, GCD(6, 4) = 2。
  • 返回 str1.substring(0, 2) = “AB”。
    示例 3：
• str1 = “LEET”, str2 = “CODE”
  • str1 + str2 = “LEETCODE”, str2 + str1 = “CODELEET” → 不相等。
  • 返回 “”。

复杂度分析

• 时间复杂度：
  • 字符串拼接和比较：O(n + m)，其中 n 和 m 分别是 str1 和 str2 的长度。
  • GCD 计算：O(log(min(n, m)))。
  • 总体时间复杂度：O(n + m)。
• 空间复杂度：
  • 拼接字符串需要 O(n + m) 的额外空间。
  • 其他操作使用常数空间。

边界情况

• 两个字符串相同：直接返回其中一个字符串。
• 一个字符串是另一个的重复：返回较短的那个字符串。
• 没有公因子：返回空字符串 “”。
• 一个字符串为空：根据题目约束，无需处理。

---

代码实现

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if(!(str1+str2).equals(str2+str1))  return "";
        int res=gcd(str1.length(),str2.length());
        return str1.substring(0,res);
    }
    public int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}