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 }; ListString ans new ArrayList(); public ListString 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); } } }为什么不用 onPathonPath常用于全排列问题用来表示某个元素在当前路径里是否已经被使用过。比如全排列中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这题可以记住一句话一个数字位置选一个对应字母不是从所有字母里做排列。遇到回溯题时先判断当前层到底是在“填位置”还是在“选或不选”不要直接套模板。