Pengjielee's blog

题目

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

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

1(!@#)  2(abc)  3(def)
4(ghi)  5(jkl)  6(mno)
7(pqrs) 8(tuv)  9(wxyz)
*(+)    0(-)      #

示例 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’] 的一个数字。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

补充

String.prototype.slice()

slice() 方法提取某个字符串的一部分，并返回一个新的字符串，且不会改动原字符串。

str.slice(beginIndex[, endIndex])

beginIndex 从该索引（以 0 为基数）处开始提取原字符串中的字符。如果值为负数，会被当做 strLength + beginIndex 看待，这里的strLength 是字符串的长度（例如，如果 beginIndex 是 -3 则看作是：strLength - 3）

endIndex 可选。在该索引（以 0 为基数）处结束提取字符串。如果省略该参数，slice() 会一直提取到字符串末尾。如果该参数为负数，则被看作是 strLength + endIndex，这里的 strLength 就是字符串的长度(例如，如果 endIndex 是 -3，则是, strLength - 3)。

JS实现

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const result = [];
  if (digits.length === 0) {
    return result;
  }

  //路径数组
  const path = [];

  //电话本的HashMap
  const phoneMap = new Map();
  phoneMap.set("2", "abc");
  phoneMap.set("3", "def");
  phoneMap.set("4", "ghi");
  phoneMap.set("5", "jkl");
  phoneMap.set("6", "mno");
  phoneMap.set("7", "pqrs");
  phoneMap.set("8", "tuv");
  phoneMap.set("9", "wxyz");

  // 深度优先遍历
  const dfs = (index, path) => {
    // 递归的终止条件
    if (index === digits.length) {
      result.push(path.slice(0).join(''));
      return;
    }
    //charAt() 方法可返回指定位置的字符。第一个字符位置为 0
    const digit = digits.charAt(index);
    // 根据数字获取其对应的字母
    const letters = phoneMap.get(digit);
    for (let letter of letters) {
      // 添加到路径数组
      path.push(letter);
      // 考查下标+1
      dfs(index + 1, path);
      // 回溯
      path.pop();
    }
  };

  //下标为0开始考查
  dfs(0, path);

  return result;
};