Skip to main content

电话号码的字母组合（ing

一、题目描述​

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

点击查看原题

示例1​

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例2​

输入：digits = ""
输出：[]

示例3​

输入：digits = "2"
输出：["a","b","c"]

提示​

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

二、题解​

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）