題目描述

??給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

解析

??廣度優先遍歷或者深度優先遍歷兩種方式，廣度優先類似構造一顆樹形結構，子樹就是當前節點加下一層數字對應的字母。

public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<>();if (digits == null || digits.length() == 0) {return res;}Map<Character, String> phoneMap = new HashMap<Character, 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");}};Queue<String> queue = new ArrayDeque<>();queue.offer("");for (int i = 0; i < digits.length(); i++) {char curDigit = digits.charAt(i);String curString = phoneMap.get(curDigit);int size = queue.size();for (int j = 0; j < size; j++) {String parentStr = queue.poll();for (int k = 0; k < curString.length(); k++) {queue.offer(parentStr + curString.charAt(k));}}}while (!queue.isEmpty()) {res.add(queue.poll());}return res;}

??深度優先遍歷利用遞歸操作，使用一個變量去記錄當前字符串的長度，達到長度后則放入結果數組中，使用字符數組可以直接覆蓋回溯。

public static List<String> letterCombinations(String digits) {List<String> res = new ArrayList<>();if (digits == null || digits.length() == 0) {return res;}Map<Character, String> phoneMap = new HashMap<Character, 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");}};char[] current = new char[digits.length()];backtrack(res, phoneMap, digits, 0, current);return res;}private static void backtrack(List<String> res, Map<Character, String> phoneMap, String digits, int index, char[] current) {if (index == digits.length()) {res.add(new String(current));return;}char digit = digits.charAt(index);String letters = phoneMap.get(digit);for (int i = 0; i < letters.length(); i++) {current[index] = letters.charAt(i);backtrack(res, phoneMap, digits, index + 1, current);}}