解题思路需要构想好回溯树的宽度和深度分别代表什么含义宽度abc或其他数字对应的字母排列for循环使用深度digits的长度递归深度使用index 1注意终止条件是if (index digits.length())下标到了最后一个元素的后一个位置最后一个元素已经处理完成而不是if (index digits.length()-1)下标到了最后一个元素的位置最后一个元素还没有开始处理StringBuffer的方法删除最后一个元素用path.deleteCharAt(path.length() - 1);这里的 i 是从0开始的因为每次处理一个新的字母组而之前的问题中每次处理的是同一个nums数组所以之前用start来防止选到前面的元素class Solution { ListString res new ArrayList(); StringBuffer path new StringBuffer(); String[] map { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; public ListString letterCombinations(String digits) { if (digits.length() 0) return res; backtracking(digits, 0); return res; } public void backtracking(String digits, int index) { if (index digits.length()) { res.add(path.toString()); return; } int digit digits.charAt(index) - 0; String str map[digit]; for (int i 0; i str.length(); i) { path.append(str.charAt(i)); backtracking(digits, index 1); path.deleteCharAt(path.length() - 1); } } }将String数组改为Map也可以做略微修改即可方法如下class Solution { ListString res new ArrayList(); StringBuffer path new StringBuffer(); MapCharacter, String map new HashMapCharacter, String() { { put(2, abc); put(3, def); put(4, ghi); put(5, jkl); put(6, mno); put(7, pqrs); put(8, tuv); put(9, wxyz); } }; public ListString letterCombinations(String digits) { if (digits.length() 0) return res; backtracking(digits, 0); return res; } public void backtracking(String digits, int index) { if (index digits.length()) { res.add(path.toString()); return; } char digit digits.charAt(index); String str map.get(digit); for (int i 0; i str.length(); i) { path.append(str.charAt(i)); backtracking(digits, index 1); path.deleteCharAt(path.length() - 1); } } }
