LeetCode 17. 电话号码的字母组合
题目描述
给定一个仅包含数字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
这题可以记住一句话：
一个数字位置选一个对应字母，不是从所有字母里做排列。遇到回溯题时，先判断当前层到底是在“填位置”，还是在“选或不选”，不要直接套模板。