每天一道leetcode(Day 32)

17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例

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

**说明:**尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解题思路

官方题解，用回溯法。

• 定义回溯函数 trace_back(combination, next_digits) ，它将一个目前已经产生的组合 combination 和接下来准备要输入的数字 next_digits 作为参数。
• 如果没有更多的数字需要被输入，那意味着当前的组合已经产生好了。
• 如果还有数字需要被输入：
  遍历下一个数字所对应的所有映射的字母。将当前的字母添加到组合最后，也就是 combination = combination + letter 。
• 重复这个过程，输入剩下的数字： trace_back(combination + letter, next_digits[1:]) 。

代码

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const phoneObj = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
  };
  let res = [];
  function trace_back(combination, nextDigits) {
    if (nextDigits.length === 0) {
      res.push(combination);
    } else {
      const digit = nextDigits.substring(0, 1);
      const letters = phoneObj[digit];
      for (let letter of letters) {
        trace_back(combination + letter, nextDigits.substring(1));
      }
    }
  }
  if (digits.length) trace_back("", digits);
  return res;
};

参考

17. 电话号码的字母组合