17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
所有组合--> 搜索-->深度优先。
问题可以分解为当前问题+子问题。
例如：问题“234” 可以分解成: 2对应的3种可能a + ans("34"),b+ans("34),c+ans("34“)
public List<String> letterCombinations(String digits) { List<String> combinations = new ArrayList<>(); if (digits.length() == 0) { return combinations; } Map<Character, 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(combinations, phoneMap, digits, 0, new StringBuffer()); return combinations; } //回溯算法，深度优先搜索 public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) { if (index == digits.length()) { combinations.add(combination.toString()); } else { char digit = digits.charAt(index); String letters = phoneMap.get(digit); for (int i = 0; i < letters.length(); i++) { combination.append(letters.charAt(i)); backtrack(combinations,phoneMap,digits,index+1,combination); combination.deleteCharAt(index); } } }
