题目描述

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。

答案可以按任意顺序返回。

数字到字母的映射与电话按键相同：

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"]

初始思路

一开始我把这题当成了全排列问题处理。

我的想法是：用onPath记录已经选择过的字母，然后在每一层递归中遍历所有digits对应的字母，避免同一个字母重复选择。

这个思路的问题在于：它套用了全排列模板，但这题不是全排列。

全排列关注的是：

从一堆候选元素里选出一个排列，每个元素通常只能用一次。

而电话号码的字母组合关注的是：

每个数字位置，只能从这个数字对应的字母中选一个。

所以这题不需要onPath，也不应该每层遍历所有数字。

解题思路

这题的关键是先明确递归函数的含义。

定义：

dfs(i)：当前正在决定 digits[i] 这一位应该选择哪个字母

对于digits = "23"：

第 0 位数字是 2，只能从 "abc" 中选一个 第 1 位数字是 3，只能从 "def" 中选一个

搜索过程是：

a -> d/e/f b -> d/e/f c -> d/e/f

也就是每一层只处理当前位置digits[i]，而不是重新遍历所有数字。

递归流程：

1. 如果 digits 为空，直接返回空列表 2. dfs(i) 表示正在决定第 i 位数字对应的字母 3. 找到 digits[i] 对应的字符串 letters 4. 遍历 letters 中的每个字符 c 5. 把 c 放入 path[i] 6. 递归 dfs(i + 1) 7. 当 i == digits.length 时，path 已经填满，加入答案

代码实现

class Solution { String[] mapping = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; List<String> ans = new ArrayList<>(); public List<String> letterCombinations(String digits) { if (digits.length() == 0) { return ans; } char[] path = new char[digits.length()]; dfs(digits.toCharArray(), 0, path); return ans; } public void dfs(char[] digits, int i, char[] path) { if (i == digits.length) { ans.add(new String(path)); return; } int idx = digits[i] - '0'; for (char c : mapping[idx].toCharArray()) { path[i] = c; dfs(digits, i + 1, path); } } }

为什么不用 onPath

onPath常用于全排列问题，用来表示某个元素在当前路径里是否已经被使用过。

比如全排列中：

nums = [1, 2, 3]

同一个排列里，1不能重复使用。

但这题不是这样。每一位数字都独立选择一个对应字母。

比如：

digits = "22"

合法结果包括：

aa, ab, ac, ba, bb, bc, ca, cb, cc

如果使用onPath禁止重复字母，aa、bb、cc就会被错误排除。

所以这题的核心不是“字母能不能重复使用”，而是：

当前位置的数字，决定了当前位置可以选择哪些字母。

易错点

1. 把题目误套成全排列模板

错误方向是：

每一层遍历所有 digits，再遍历每个 digit 对应的字母。

这样会打乱数字位置和字母选择之间的关系。

正确方向是：

第 i 层只处理 digits[i]

2. 错误使用 onPath

这题不需要记录某个字母是否已经选过。

每个数字位置只负责选自己的字母，递归进入下一层时自然会处理下一个数字。

3. 漏掉空字符串特判

当digits = ""时，题目要求返回：

[]

如果不特判，递归一开始就会满足：

i == digits.length

然后把空字符串加入答案，返回：

[""]

这是不符合题意的。

复杂度分析

设n = digits.length()。

每个数字最多对应 4 个字母，所以组合数量最多是4^n。

• 时间复杂度：O(n * 4^n)。最多有4^n个组合，每个组合转成字符串需要O(n)。
• 空间复杂度：O(n)。递归栈和path长度都是n；如果把返回结果也计入空间，则为O(n * 4^n)。

复盘

这题最重要的是不要把所有回溯题都套成同一个模板。

全排列的模型是：

每一层从所有未使用元素中选一个。

电话号码字母组合的模型是：

每一层只处理当前位置的数字，从这个数字对应的字母中选一个。

所以递归定义应该从“当前处理第几个数字”出发：

dfs(i)：决定 digits[i] 这一位的字母

只要这个定义清楚，path[i] = c、dfs(i + 1)、i == digits.length这些代码就都很自然。

Tips

这题可以记住一句话：

一个数字位置选一个对应字母，不是从所有字母里做排列。

遇到回溯题时，先判断当前层到底是在“填位置”，还是在“选或不选”，不要直接套模板。