.jpg)
650 字
3 分钟
电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解题思路
- 回溯法框架：
- 建立数字-字母映射表
- 递归处理每个数字，遍历其对应字母
- 当前路径添加字母后进入下一层递归
- 路径长度等于输入数字串时保存结果
- 队列迭代法：
- 初始化队列为空组合
[""] - 遍历每个数字，将队列中组合与当前数字字母组合
- 生成新组合并入队
- 初始化队列为空组合
- DFS/BFS选择：
- 回溯法本质是DFS，空间效率高
- 迭代法为BFS，无递归开销
关键洞察
- 笛卡尔积本质：
- 每个数字对应一组字母
- 最终结果 = 各数字对应字母集的笛卡尔积
- 递归深度控制：
- 递归深度 = 输入数字串长度
- 每层对应一个数字的选择
- 无剪枝需求：
- 所有组合均有效，无需剪枝
- 映射表优化：
- 预处理映射表避免重复查询
- 支持灵活扩展字母映射
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(3ᴺ × 4ᴹ)：N为3字母数字数，M为4字母数字数（7/9） |
| 空间复杂度 | O(L)：递归栈深度L（输入长度）+ 结果空间 O(3ᴺ × 4ᴹ) |
代码实现
回溯法
/** * @link {https://leetcode.cn/problems/letter-combinations-of-a-phone-number/} * @param {string} digits * @return {string[]} */const letterCombinations = (digits) => { if (!digits) return [];
// 数字-字母映射 const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
const res = []; const backtrack = (index, path) => { // 完成组合：保存路径 if (index === digits.length) { res.push(path); return; }
// 遍历当前数字对应字母 const letters = map[digits[index]]; for (const char of letters) { backtrack(index + 1, path + char); // 递归下一层 } };
backtrack(0, ''); return res;};队列迭代法
/** * @link {https://leetcode.cn/problems/letter-combinations-of-a-phone-number/} * @param {string} digits * @return {string[]} */var letterCombinations = function (digits) { if (!digits.length) return [];
const map = { '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z'] };
let queue = [''];
for (const digit of digits) { const nextQueue = []; const letters = map[digit];
for (const str of queue) { for (const char of letters) { nextQueue.push(str + char); } }
queue = nextQueue; }
return queue;};