递归
自己写了个递归的算法
class Solution {
public List<String> letterCombinations(String digits) {
List<String> resList = recursion(digits);
return resList;
}
public List<String> recursion(String str) {
List<String> resList = new ArrayList<>();
if (str.isEmpty()) {
return resList;
}
if (str.length() == 1) {
String s = getStr(str.charAt(0));
for (int i = 0; i < s.length(); i++) {
resList.add(s.substring(i, i+1));
}
return resList;
}
List<String> list = recursion(str.substring(1));
for (int j = 0; j < list.size(); j++) {
String s = getStr(str.charAt(0));
for (int k = 0; k < s.length(); k++) {
String item = s.charAt(k) + list.get(j);
resList.add(item);
}
}
return resList;
}
public String getStr(char c) {
String[] buttons = {"", "", "abc", // 0, 1, 2
"def", "ghi", "jkl", // 3, 4, 5
"mno", "pqrs", "tuv", "wxyz"}; // 6, 7, 8, 9
int index = c - '0';
return buttons[index];
}
}
回溯
题解中给的一种回溯解法
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>();
if (digits.length() == 0) {
return combinations;
}
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");
}};
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);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
combination.append(letters.charAt(i));
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.deleteCharAt(index);
}
}
}
}