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

英文原文

For two strings s and t, we say "t divides s" if and only if s = t + ... + t  (t concatenated with itself 1 or more times)

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

 

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Example 4:

Input: str1 = "ABCDEF", str2 = "ABC"
Output: ""

 

Constraints:

• 1 <= str1.length <= 1000
• 1 <= str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

中文题目

对于字符串 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. 1 <= str1.length <= 1000
2. 1 <= str2.length <= 1000
3. str1[i] 和 str2[i] 为大写英文字母

通过代码

高赞题解

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

const gcd = (a, b) => (0 === b ? a : gcd(b, a % b))

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

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

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

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

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

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

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

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

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

[]
var gcdOfStrings = function(str1, str2) {
  if (str1 + str2 !== str2 + str1) return ''
  const gcd = (a, b) => (0 === b ? a : gcd(b, a % b))
  return str1.substring(0, gcd(str1.length, str2.length))
};

统计信息

通过次数	提交次数	AC比率
35166	59914	58.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言