No.1071 字符串的最大公因子

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

给定两个字符串 str1 和 str2 。返回 最长字符串 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, str2.length <= 1000
• str1 和 str2 由大写英文字母组成

解题思路

最大公约数 + 数学法，计算前缀串，若 str1 + str2 = str2 + str1，那么一定存在符合条件的 x

实现

完整逻辑

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
  // 求最大公约数
  function gcd(a, b) {
    let rest = a % b;
    while (rest !== 0) {
      a = b;
      b = rest;
      rest = a % b;
    }
    return b;
  }
  if (str1 + str2 !== str2 + str1) return "";
  return str1.substring(0, gcd(str1.length, str2.length));
};

简化逻辑

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
  // 求最大公约数
  function gcd(a, b) {
    let [x, y] = [a, b];
    while (y !== 0) {
      [x, y] = [y, x % y];
    }
    return x;
  }
  if (str1 + str2 !== str2 + str1) return "";
  return str1.substring(0, gcd(str1.length, str2.length));
};