复盘 · LC 17 电话号码的字母组合

题目

题号：LeetCode 17
名称：电话号码的字母组合（Letter Combinations of a Phone Number）
难度：Medium
链接：leetcode.cn/problems/letter-combinations-of-a-phone-number
今日代码：17-电话号码的字母组合/index.js

题意

给定仅含数字 2-9 的字符串 digits，返回它能表示的所有字母组合（老式手机九宫格映射）。

映射：2→abc, 3→def, …, 9→wxyz。
digits 为空时返回 []（LeetCode 约定）。
边界：一位数字（如 "2"）返回 ["a","b","c"]；含 7、9 的四字母键。

涉及算法

标签	一句话
回溯 / DFS	按位枚举当前数字对应的每个字母，到底拼接成串
多叉树遍历	深度 = `digits.length`，每层分支数 = 当前键字母个数

教程对照：19 · 递归心智与回溯框架（固定深度回溯，与子集「可变长路径」对比）。

评价我的解法

整体是标准 DFS：建映射表 → 递归到 index === digits.length 收集 → 每位 for 循环试字母。函数名叫 bfs 实际是深度优先，命名会误导自己。

我的代码（摘自 17-电话号码的字母组合/index.js，不含测例）：

javascript

var letterCombinations = function (digits) {
  const letterMap = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };
  for (const key of Object.keys(letterMap)) {
    const value = letterMap[key];
    letterMap[key] = value.split("");
  }
  const resArr = [];
  const tmpResArr = [];
  function bfs(index) {
    if (index >= digits.length) {
      resArr.push(tmpResArr.join(""));
      return;
    }
    const letterArr = letterMap[digits[index]];
    for (const l of letterArr) {
      tmpResArr[index] = l;
      bfs(index + 1);
    }
  }
  bfs(0);
  return resArr;
};

优点：

映射预处理成数组，内层 for (const l of letterArr) 干净。
用 tmpResArr[index] = l 代替 push/pop：深度固定，写法正确且省 pop。
测例 "23" 通过，用时 0 ms，说明主逻辑没问题。

可改进点：

缺空串边界：digits === "" 时仍会 push("") 进结果，LeetCode 要求 []；开头加 if (!digits.length) return [] 即可。
函数名 bfs：应叫 dfs，和层序 BFS 区分。
tmpResArr 长度：递归过程中数组会稀疏，靠 join("") 拼串没问题；若改用 path.push / path.pop 更接近通用回溯模板，面试口述更顺。

小结：四题里这题最稳；补空串判断 + 统一命名，就是可直接默写的模板。

最佳题解

通用 push/pop 版（与子集、组合同一套口述）：

javascript

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

  const map = {
    2: "abc", 3: "def", 4: "ghi", 5: "jkl",
    6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz",
  };
  const res = [];
  const path = [];

  function dfs(i) {
    if (i === digits.length) {
      res.push(path.join(""));
      return;
    }
    for (const ch of map[digits[i]]) {
      path.push(ch);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
};

时间 O(4^n · n) 量级（n = digits 长度，最坏每键 4 字母），空间 O(n) 栈深。
与你写法等价；push/pop 更利于迁移到全排列、组合总和。

关联题目

题	为何相关
22. 括号生成	同是「逐位做选择」的回溯，约束不同
46. 全排列	每层可选集合变化，需 used 标记
79. 单词搜索	网格 DFS + 撤销
131. 分割回文串	字符串分段枚举

一句话带走

电话字母组合：深度等于位数，每层把当前键的字母试一遍，到底 join 进答案；别忘 digits 为空返回 []。

复盘 · LC 17 电话号码的字母组合 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​