「每日LeetCode」2021年4月25日

本文最后更新于：2023年3月19日 晚上

Lt1071. 字符串的最大公因子

1071. 字符串的最大公因子

对于字符串 S 和 T，只有在 S = T + ... + T（T 自身连接 1 次或多次）时，我们才认定  “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
 示例 1：

1
2
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：

1
2
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：

1
2
输入：str1 = "LEET", str2 = "CODE"
输出：""

提示：

  1. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i] 和 str2[i] 为大写英文字母

思路

从短的字符串开始，求每一个子串是否都能将 str1str2 完全分隔成全为空的数组，可以的话更新 res。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
  const str = str1.length > str2.length ? str1 : str2;
  let temp = "";
  let res = "";
  for (const char of str) {
    temp += char;
    const arr1 = str1.split(temp);
    const arr2 = str2.split(temp);
    if (arr1.every((e) => e === "") && arr2.every((e) => e === "")) res = temp;
  }
  return res;
};