leetcode第17题 电话号码的组合

思路:

1. 还是很典型的回溯思路，穷举，列出所有的代码组合
2. 画出递归树，一层一层的遍历，遇到合适的情况，加入到结果集里面。
3. 柑橘和全排列有一点像，可以类比这看一看。

class Solution {HashMap<Integer, String> map;public List<String> letterCombinations(String digits) {map = new HashMap<>();map.put(2, "abc");map.put(3, "def");map.put(4, "ghi");map.put(5, "jkl");map.put(6, "mno");map.put(7,"pqrs");map.put(8,"tuv");map.put(9,"wxyz");List<String> list = new LinkedList<>();if (digits.length() == 0) {return list;}backTrack(0,digits,new String(),list);return list;}public void backTrack(int index, String digits, String path, List<String> list) {if (index >= digits.length()) {list.add(path);return;}//这里进行一点一点的回溯int c = Integer.parseInt(digits.charAt(index) + "");String s = map.get(c);for (int i = 0; i < s.length(); i++) {path += s.charAt(i);backTrack(index + 1,digits,path,list);path = path.substring(0,path.length() - 1);}}
}