LeetCode1071. 字符串的最大公因子
题目描述
对于字符串 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 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
思路
1、最大公因子的长度应该小于等于两个字符串中较小的那个
2、先假设长度较小的为最大公因子
3、验证不通过则不断缩短最大公因子的长度
4、验证通过返回当前字符串即为答案
代码：
/** * @param {string} str1 * @param {string} str2 * @return {string} */ var gcdOfStrings = function(str1, str2) { let gcd = function(s1,s2){ let i = s2.length / s1.length,res = ""; if(s2.length % s1.length != 0) return false; while(i--) res = res + s1; return res == s2; }; let mins = str1.length > str2.length ? str2 : str1, maxs = str1.length > str2.length ? str1 : str2, minl = str2.length > str1.length ? str1.length : str2.length; while(minl){ let s = mins.substring(0,minl); if(gcd(s,mins) && gcd(s,maxs)) return s; minl--; } return ""; };
