字符串的最大公因子
题目
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
示例
示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
示例 3：
输入：str1 = "LEET", str2 = "CODE"
输出：""
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
渐进题解 1
1、比较获得 `较短字符串`
2、循环 `较短字符串` ， 逐个累加字符作为 `测试字符串`
3、
若 `较长字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较长字符串` 不可能被 `测试字符串` 整除
若 `较短字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较短字符串` 不可能被 `测试字符串` 整除
4、若长度能被整除，整除得到的倍数称之为 `times1` `times2`
使 `测试字符串长度` 复制 `times1` `次、times1` 次
若分别能等于 `较长字符串` 、 `较短字符串` 则满足 `公因数字符串` ，将该 `公因数字符串` 存起来，继续循环
5、最后一个 `公因数字符串` 既是 `最大公因数字符串`
渐进题解 2
1、比较获得 `较短字符串`
2、循环 `较短字符串` ，
根据题目 `S = N * T`
使用 `较短字符串` 截取 `自身` 、 `自身一半` `、自身四分之一` ... 得到 `测试字符串`
3、
若 `较长字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较长字符串` 不可能被 `测试字符串` 整除
若 `较短字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较短字符串` 不可能被 `测试字符串` 整除
4、若长度能被整除，整除得到的倍数称之为 `times1` `times2`
使 `测试字符串长度` 复制 `times1` `次、times1` 次
若分别能等于 `较长字符串` 、 `较短字符串` 则满足 `公因数字符串`
5、因为是使用 `尽可能取最大公因数字符串` 的方法去测试验证的，所以只要满足条件，就是 `最大公因数字符串`
此时的 `公因数字符串` 就是 `最大公因数字符串`
力扣教好题解
1、若满足都能被 `X` 除尽，那么这两个字符串 `正序相加` 与 `反序相加` 之后的的结果应该相等
2、`辗转相除法` 求得 `最大公因数长度` ，对随便一个字符串进行截取`（0, 最大公因数长度）`即可得到 `X`
定理：gcd(a, b) = gcd(b, a % b)
而任何数与0的最大公约数是它本身 （递归终止条件）
题解
渐进题解 1
// 用时一般，内存消耗一般
执行用时: 68 ms
内存消耗: 37.8 MB
let gcdOfStrings = function(str1, str2) {
// 使得 str2 是较短字符串
if (str1.length < str2.length) {
[str1, str2] = [str2, str1]
}
let cfstr = '' // 测试字符串
let list = [] // 公因数字符串数组
let s1len = str1.length
let s2len = str2.length
for (const s of str2) {
// 累加得到 测试字符串
cfstr += s
// 若 `较长字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较长字符串` 不可能被 `测试字符串` 整除
// 若 `较短字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较短字符串` 不可能被 `测试字符串` 整除
// 若长度能被整除，整除得到的倍数称之为 `times1` `times2`
// 使 `测试字符串长度` 复制 `times1` `次、times1` 次
// 若分别能等于 `较长字符串` 、 `较短字符串` 则满足 `公因数字符串` ，将该 `公因数字符串` 存起来，继续循环
if (cfstr.repeat(s1len / cfstr.length) === str1 && cfstr.repeat(s2len / cfstr.length) === str2) list.push(cfstr)
}
// 最后一个 `公因数字符串` 既是 `最大公因数字符串`
return list.pop() || ''
}
渐进题解 2
// 用时一般，内存消耗一般
执行用时: 52 ms
内存消耗: 33.9 MB
let gcdOfStrings = function(str1, str2) {
// 使得 str2 是较短字符串
if (str1.length < str2.length) {
[str1, str2] = [str2, str1]
}
let s1len = str1.length
let s2len = str2.length
let cfstr = '' // 测试字符串
let cflen = s2len // 测试字符串长度
let times = 1 // 倍数
while(times < s2len) {
// 根据题目 S = N * T
// 使用较短字符串截取 自身 、 自身一半 、自身四分之一 ...
// 得到 `测试字符串`
cfstr = str2.slice(0, cflen / times)
// 若 `较长字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较长字符串` 不可能被 `测试字符串` 整除
// 若 `较短字符串的长度` 不能被 `测试字符串长度` 整除，那这个 `较短字符串` 不可能被 `测试字符串` 整除
// 若长度能被整除，整除得到的倍数称之为 `times1` `times2`
// 使 `测试字符串长度` 复制 `times1` `次、times1` 次
// 若分别能等于 `较长字符串` 、 `较短字符串` 则满足 `公因数字符串`
// 因为是使用 `尽可能取最大公因数字符串` 的方法去测试验证的，所以只要满足条件，就是 `最大公因数字符串`
// 此时的 `公因数字符串` 就是 `最大公因数字符串`
if (cfstr.repeat(s1len / cfstr.length) === str1 && cfstr.repeat(s2len / cfstr.length) === str2) return cfstr
times++
}
return ''
}
力扣教好题解
// 用时一般，内存消耗一般
执行用时: 64 ms
内存消耗: 33.8 MB
// 辗转相除法
// 定理：gcd(a, b) = gcd(b, a % b)
// 而任何数与0的最大公约数是它本身 （递归终止条件）
// 更相减损术
// 原理：gcd(a, b) = gcd(b, a - b)
// 两个正整数 a 和 b（a > b），它们的最大公约数等于 a - b 的差值c和较小数b的最大公约数
const gcd = (a, b) => {
return b === 0 ? a : gcd(b, a % b)
}
let gcdOfStrings = function(str1, str2) {
// 若满足都能被 X 除尽，那么这两个字符串 正序与反序相加的结果应该相等
if (str1 + str2 !== str2 + str1) return ''
// 使用辗转相除法得到最大公因数，对随便一个字符串进行截取即可得到 X
return str1.slice(0, gcd(str1.length, str2.length))
}