1071 Greatest Common Divisor of Strings

题目

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

Return the largest string X such that X divides str1 and X divides str2.

Example 1:

1
2
3

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

1
2
3

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

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

Note:

1
2
3

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.

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

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

解题思路

先判断是否存在子字符串(以下称为子串) x 能同时除尽 str1 和 str2.
如果存在子串 x,则最长子串的长度一定是 str1 和 str2 长度的最大公约数.

如果存在子串 x 能同时除尽 str1 和 str2.
则 str1 和 str2 一定是 x 的重复序列. str1 + str2 一定等于 str2 + str1.

ABABAB + ABAB == ABAB + ABABAB

否则一定不存在子串 x.例如:

ABABAB + ABA != ABA + ABABAB

当有子串 x 可以同时除尽 str1 和 str2 时, 子串 x 一定满足如下条件:
(令 xLen 为 x.length, str1Len 和 str2Len 分别为 str1.length str2.length)

1 子串 x 的长度 xLen 一定是 str1Len 和 str2Len 的公约数, 即 str1Len 和 str2Len 一定是 xLen 的倍数.

str1.length % x.length = 0
str2.length % x.length = 0

2 根据公约数性质, str1Len 和 str2Len 的公约数一定是 gcd(str1Len, str2Len) (str1Len 和 str2Len 的最大公约数)的约数.
如果存在子串 x , 则其长度 xLen 一定是 gcd(str1Len, str2Len) 的约数,gcd(str1Len, str2Len) 一定是 xLen 的倍数.

$gcd(str1Len, str2Len) = k \cdot xLen (k > 0)$

(令 xg 为 str1 和 str2 中长度为 gcd(str1Len, str2Len) 的子串. xgLen 为 xg.length)
因为 xg 是 x 的倍数, 且 xgLen 是 str1Len 和 str2Len 的最大公约数.
所以 xg 一定是可以同时除尽 str1 和 str2 的最长字串.

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcd = function(a, b) {
    if (a , b) {
        [a, b] = [b, a]
    }
    while(b > 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
var gcdOfStrings = function(str1, str2) {
    if (str1 + str2 !== str2 + str1) {
        return ''
    }
    return str1.slice(0, gcd(str1.length, str2.length));
};

参考

维基百科最大公约数