17. 电话号码的字母组合 (Medium)
专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个仅包含数字 2-9 的字符串 digits，返回所有它能表示的字母组合。答案可以按任意顺序返回。
数字到字母的映射与电话按键相同：
- 2 → abc，3 → def，4 → ghi，5 → jkl
- 6 → mno，7 → pqrs，8 → tuv，9 → wxyz
示例 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']的一个数字
题目详细分析
数据范围含义：
digits.length <= 4：最多 4 位数字，最坏情况是 7 或 9（对应 4 个字母），4^4 = 256 种组合，完全在可枚举范围内。- 输入可能为空字符串，此时返回空列表，这是必须处理的边界情况。
核心约束：
- 每个数字对应一组字母，从每组中选一个字母进行组合。
- 组合结果的长度必须等于输入数字的个数。
- 数字 1 不在映射范围内，题目保证输入只有 2-9。
与全排列的区别：
- 全排列中每一层的选择列表相同（未使用的全部元素），而这里每一层的选择列表由当前数字决定，每层不同。
小白版直白理解
就像老式手机键盘，按 “23” 时：
- 按 2 可以选 a/b/c
- 按 3 可以选 d/e/f
你要把所有可能的字母组合列出来：a 搭配 d/e/f 得到 ad、ae、af，b 搭配 d/e/f 得到 bd、be、bf，c 搭配 d/e/f 得到 cd、ce、cf。
就像到了自助餐厅，第 1 道菜有 3 种选择，第 2 道菜有 3 种选择，你把所有搭配方式都试一遍。
解题思路
思路一：回溯法（推荐）
核心思想： 逐位处理每个数字，当前数字对应的每个字母都是一个分支。这是一个多叉树的遍历问题——每层的分支数取决于当前数字对应几个字母。
决策树可视化（以 “23” 为例）：
""
/ | \
a b c
/ | \ / | \ / | \
d e f d e f d e f
ad ae af bd be bf cd ce cf
def letterCombinations(digits):
if not digits:
return []
# 数字到字母的映射表
mapping = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
res = []
def backtrack(idx, path):
# 终止条件：处理完所有数字
if idx == len(digits):
res.append(''.join(path))
return
# 获取当前数字对应的所有字母
letters = mapping[digits[idx]]
for ch in letters:
path.append(ch) # 做选择
backtrack(idx + 1, path) # 递归处理下一个数字
path.pop() # 撤销选择
backtrack(0, [])
return res思路二：队列迭代法（BFS）
核心思想： 使用队列逐位生成组合。每处理一个数字，将当前队列中的所有字符串与当前数字的每个字母组合，生成新的队列。
def letterCombinations(digits):
if not digits:
return []
mapping = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
from collections import deque
queue = deque(['']) # 初始队列包含一个空字符串
for digit in digits:
letters = mapping[digit]
# 处理当前层的所有字符串
for _ in range(len(queue)):
s = queue.popleft()
for ch in letters:
queue.append(s + ch)
return list(queue)时间复杂度： O(4^n)，空间复杂度：O(4^n)（队列中最多同时存放 O(4^n) 个元素）。
易错点
- 空输入处理：
digits = ""应该返回[]而不是[""]。需在开头做特判。 - 数字与字符串混淆：映射表的 key 是字符串
'2'而不是整数2，用digits[idx]获取的也是字符。 - 回溯终止条件：
idx == len(digits)时记录结果，此时path的长度也等于len(digits)。 - 数字 7 和 9 对应 4 个字母：不要遗漏 7→pqrs 和 9→wxyz 的第 4 个字母。
- 索引递增：递归调用
backtrack(idx + 1, ...)而不是backtrack(idx++, ...)或忘记递增。
框架提炼
多叉树回溯模板（每层选择列表不同）：
def backtrack(层数, 路径):
if 层数 == 总层数:
记录结果
return
当前层选择列表 = get_choices(层数)
for 选择 in 当前层选择列表:
路径.append(选择)
backtrack(层数 + 1, 路径)
路径.pop()与标准回溯的区别：
- 标准回溯（全排列）每层的选择列表相同，通过 visited 排除已选。
- 本题每层的选择列表都由当前数字决定，层与层之间不同。
- 没有”剪枝”需求，因为所有路径都是合法的。