給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合择诈。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母出皇。
示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說明:
盡管上面的答案是按字典序排列的吭从，但是你可以任意選擇答案輸出的順序。
解法一：
迭代求解恶迈。
public List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<>();
if (digits.isEmpty()) {
return list;
}
String[] strings = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
list.add("");
//對所有數(shù)字進行遍歷
for (int i = 0; i < digits.length(); i++) {
//得到對應(yīng)數(shù)字的字符串
String str = strings[digits.charAt(i) - '2'];
//獲取當前列表中的字符串個數(shù)
int size = list.size();
//對列表中的字符串進行遍歷
for (int j = 0; j < size; j++) {
//獲取列表第一個字符串
String temp = list.get(0);
//然后刪除它，因為該字符串不完整谱醇，所以不是我們要的答案
list.remove(0);
//然后遍歷之前獲得的對應(yīng)數(shù)字的字符串暇仲，逐個添加字符，然后添加進列表
for (int k = 0; k < str.length(); k++) {
list.add(temp + str.charAt(k));
}
}
}
return list;
}
解法二：
遞歸求解副渴。我們需要建立一個字典奈附，用來保存每個數(shù)字所代表的字符串，然后我們還需要一個變量 level煮剧，記錄當前生成的字符串的字符個數(shù)斥滤。
public List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<>();
if (digits.isEmpty()) {
return list;
}
String[] strings = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
letterCombinationsDFS(digits, strings, 0, new StringBuilder(), list);
return list;
}
public void letterCombinationsDFS(String digits, String[] strings, int level, StringBuilder out, List<String> list) {
//如果已經(jīng)到達最后一層将鸵，則把字符串添加進列表
if (level == digits.length()) {
list.add(out.toString());
} else {
//獲取對應(yīng)數(shù)字的字符串
String str = strings[digits.charAt(level) - '2'];
for (int i = 0; i < str.length(); i++) {
out.append(str.charAt(i));
//添加完這一層的一個字符之后，繼續(xù)添加下一層的字符
letterCombinationsDFS(digits, strings, level + 1, out, list);
//注意要回退字符串
out.deleteCharAt(out.length() - 1);
}
}
}
本題思路參考自 [LeetCode] Letter Combinations of a Phone Number 電話號碼的字母組合
