难度: Medium
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。运行时间: 44 ms
内存: 15 MB
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
m = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
ans = []
def backtrack(path):
if len(path) == len(digits):
ans.append(''.join(path))
return
choices = m[digits[len(path)]]
for char in choices:
path.append(char)
backtrack(path)
path.pop()
backtrack([])
return ans
这个题解使用回溯算法来解决电话号码的字母组合问题。首先，定义了一个字典 m，将数字映射到对应的字母。然后定义一个辅助函数 backtrack，它接受一个路径参数 path。在函数中，如果 path 的长度等于 digits 的长度，说明找到了一个完整的字母组合，将其加入答案列表 ans 中。否则，根据当前 path 的长度，从 digits 中取出对应的数字，并获取该数字对应的字母选择。遍历这些字母选择，将每个字母加入 path，递归调用 backtrack，然后在回溯时将该字母从 path 中移除。最后，在主函数中调用 backtrack([])，并返回答案列表 ans。
时间复杂度: O(m^n * n)
空间复杂度: O(m^n * n)
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
# 定义数字到字母的映射
m = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
ans = []
def backtrack(path):
# 如果 path 的长度等于 digits 的长度，说明找到了一个完整的字母组合
if len(path) == len(digits):
ans.append(''.join(path))
return
# 获取当前位置的数字对应的字母选择
choices = m[digits[len(path)]]
# 遍历字母选择，递归生成字母组合
for char in choices:
path.append(char)
backtrack(path)
path.pop() # 回溯，移除当前选择的字母
backtrack([])
return ans
在题目中，每个数字对应几个可能的字母，而`digits`代表了用户输入的数字序列。当`path`的长度与`digits`长度相等时，意味着已经为`digits`中的每个数字选择了一个对应的字母，形成了一个完整的字母组合。这种组合正好对应着`digits`输入的一个有效解释，即一个可能的字母组合。因此，这时可以认为找到了一个有效的字母组合，应当将其加入到答案列表中。
在`backtrack`函数中，`path.pop()`操作用于在每次递归调用后撤销前一个状态的选择，这是为了探索其他可能的字母选择，从而生成不同的字母组合。这一操作与回溯算法的特性`状态撤销`直接相关，它允许算法返回到上一个决策点，并试探其他可能的路径选择，从而全面搜索所有可能的解决方案。这种撤销和重新选择的过程是回溯算法解决组合和排列问题的核心机制。
字典`m`在算法中扮演了关键角色，它将每个数字映射到对应的一组字母上。这样，每当算法处理输入数字序列`digits`的某个数字时，可以直接通过这个映射找到该数字对应的所有可能的字母选择。这种映射简化了查找过程，提高了效率，并使得算法能够针对每个数字快速生成所有可能的字母组合。通过这种方式，`m`映射直接支持了算法的主要功能，即生成和探索所有基于输入数字的可能字母组合。