Skip to main content

字符串的最大公因子（ing

一、题目描述​

对于字符串 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、★☆☆​

使用递归的方式，两两分配后再两两分配：

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const strList = [
    [],
    [],
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
    ["j", "k", "l"],
    ["m", "n", "o"],
    ["p", "q", "r", "s"],
    ["t", "u", "v"],
    ["w", "x", "y", "z"],
  ];
  if (digits.length >= 2) {
    let resultArr = [];
    // 递归函数
    const handle = (arr) => {
      if (arr.length >= 2) {
        const addArr = [];
        arr[0].map((item1) => {
          arr[1].map((item2) => {
            addArr.push(item1 + item2);
          });
        });
        
        arr.shift();
        arr.shift();
        const newArr = [addArr, ...arr];
        // 这里替换前两个数组的操作可以直接用 splice() 实现
        handle(newArr);
      } else {
        resultArr = arr[0];
      }
    };
    const strArr = [];
    const digitsArr = digits.split("");
    digitsArr.map((item) => {
      const curNum = Number(item);
      strArr.push(strList[curNum]);
    });
    handle(strArr);
    return resultArr;
  } else if ((digits.length = 1)) {
    return strList[Number(digits)];
  } else {
    return [];
  }
};

2、★★☆​

DFS 回溯、BFS 解法（学习 ing）