电话号码的字母组合题目链接https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答int[] first new int[]{0, 3, 6, 9, 12, 15, 19, 22, 26}; StringBuilder sb new StringBuilder(); public ListString letterCombinations(String digits) { ListString ans new ArrayList(); backtrack(digits, 0, ans); return ans; } public void backtrack(String digits, int cur, ListString ans){ if(cur digits.length()){ ans.add(sb.toString()); return; } int curIndex digits.charAt(cur) - 2; //每一种字母都选一遍 for(int ifirst[curIndex]; ifirst[curIndex1]; i){ char ch (char) (i a); sb.append(ch); backtrack(digits, cur1, ans); //回溯 sb.deleteCharAt(cur); } }分析 代码的时间复杂度为O(3^m * 4^n)空间复杂度为O(mn)其中 m 是输入中对应 3 个字母的数字个数包括数字 2、3、4、5、6、8n 是输入中对应 4 个字母的数字个数包括数字 7、9mn 是输入数字的总个数。 解题思路采用递归回溯解题。用first数组维护每个数字能表示的第一个字母的下标字母下标范围为0~25递归遍历到digits中的每个数字时将此数字能表示的字母都选择一遍直到digits遍历完最后一个数字后收集答案。看了官方题解后的解答//方法回溯 //时间复杂度O(3^m * 4^n)其中 m 是输入中对应 3 个字母的数字个数包括数字 2、3、4、5、6、8n 是输入中对应 4 个字母的数字个数包括数字 7、9mn 是输入数字的总个数。 //空间复杂度O(mn) public ListString letterCombinations(String digits) { ListString ans new ArrayList(); MapCharacter, String phoneMap new HashMap(){{ put(2, abc); put(3, def); put(4, ghi); put(5, jkl); put(6, mno); put(7, pqrs); put(8, tuv); put(9, wxyz); }}; backtrack(digits, 0, new StringBuffer(), phoneMap, ans); return ans; } public void backtrack(String digits, int cur, StringBuffer sb, MapCharacter, String phoneMap, ListString ans){ if(cur digits.length()){ ans.add(sb.toString()); return; } char digit digits.charAt(cur); String letters phoneMap.get(digit); int lettersCount letters.length(); for(int i0; ilettersCount; i){ sb.append(letters.charAt(i)); backtrack(digits, cur 1, sb, phoneMap, ans); sb.deleteCharAt(cur); } }分析官方的解题思路与我的解答一致唯一的区别在于我选择用数组first维护每个数字代表的字母而官方采用哈希表维护。总结本题只需掌握基本的递归回溯方法唯一需要思考的就是如何维护每个数字代表的字母。
