LeetCode1071-字符串的最大公因子

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/greatest-common-divisor-of-strings/

中文链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/

题目详述

对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例 1：

1
2
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：

1
2
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：

1
2
输入：str1 = "LEET", str2 = "CODE"
输出：""

提示：

  • 1 <= str1.length <= 1000
  • 1 <= str2.length <= 1000
  • str1[i] 和 str2[i] 为大写英文字母

题目详解

  • 由最大公因子可以联想到求两个正整数最大公约数的一行代码 return b == 0 ? a : gcd(b, a % b)。
  • 假设 s 是 str1 与 str2 的公因子（s 不为 ""），即 str1 由 m 个 s 连接而成，str2 由 n 个 s 连接而成，显然 m + n 个 s 等同于 n + m 个 s，得到 str1 与 str2 存在最大公因子的充要条件为 (str1 + str2).equals(str2 + str1)。
  • 观察发现，字符串的最大公因子的长度就是两个字符串的长度的最大公因数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode_01071 {

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

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