0017.电话号码的字母组合
难度：🟡 中等
标签：哈希表、字符串、回溯
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
解题思路
核心思想
本题的目标是找出数字字符串对应的所有可能的字母组合。这本质上是一个组合搜索问题，因为我们需要从每个数字对应的字母集合中各选一个，来组成最终的字符串。回溯法 是解决此类问题的经典算法。
思路选择
回溯法（深度优先搜索 DFS） 是解决此问题的标准思路。我们可以把生成组合的过程想象成在一棵决策树上进行探索。
树的每一层代表输入数字字符串
digits的一个位置。每一层的选择是在当前数字对应的字母集合中挑选一个字母。
从根节点到叶子节点的一条完整路径，就构成一个字母组合。
关键步骤
处理边界情况：如果输入的
digits字符串为空，直接返回空数组。建立映射：创建一个哈希表，存储数字字符到其对应字母数组的映射。
定义回溯函数：创建一个递归函数，例如
backtrack(index, path)。index: 当前正在处理的digits字符串的索引。path: 一个数组或字符串，存储当前正在构建的字母组合。
设置终止条件 (Base Case)：当
path的长度等于digits的长度时，说明我们已经构建了一个完整的组合，将其加入结果集，并结束当前递归。循环与递归： a. 获取当前数字
digits[index]对应的字母数组。 b. 遍历这个字母数组中的每一个字母。 c. 做出选择：将当前字母追加到path的末尾。 d. 进入下一层决策：以index + 1作为新的索引，递归调用回溯函数。 e. 撤销选择：当深层递归返回后，将之前加入的字母从path中移除，以便回溯到上一状态，尝试其他的选择分支。
代码实现
// 全局映射表
let choices = {
'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']
}
// 回溯辅助函数
var backTracking = function (path, results, target, current) {
if (path.length === target.length) {
results.push(path.join(''));
return;
}
let candicate = choices[target[current]];
for (let i = 0; i < candicate.length; i++) {
path.push(candicate[i]);
backTracking(path, results, target, current + 1);
path.pop();
}
}
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
if (digits.length === 0) return [];
let results = []
backTracking([], results, digits, 0);
return results;
};
复杂度分析
时间复杂度：O(4ⁿ × n) 其中 n 是
digits的长度。在最坏的情况下（输入全是 '7' 或 '9'），每个数字对应 4 个字母。总的组合数是指数级的，对于每个组合，还需要 O(n) 的时间来join成字符串。空间复杂度：O(n) 不考虑存储结果的数组，空间复杂度主要由递归调用栈的深度决定，最深为 n。
相关题目
总结
本题是回溯算法的经典入门题。它完美地展示了如何将问题分解为一系列的选择，并通过递归的方式系统性地探索所有可能的选择路径，最终构建出所有符合条件的解。