2020-05-01 17. Letter Combinatio
17. Letter Combinations of a Phone Number
Medium
3469383Add to ListShare
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
思路：回溯算法，遇到长度合适的结果就添加到结果清单中。
class Solution {
private static char[][] numPad = new char[][]{
new char[]{},
new char[]{},
"abc".toCharArray(),
"def".toCharArray(),
"ghi".toCharArray(),
"jkl".toCharArray(),
"mno".toCharArray(),
"pqrs".toCharArray(),
"tuv".toCharArray(),
"wxyz".toCharArray()
};
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) return new ArrayList<>(0);
LinkedList<String> res = new LinkedList<>();
char[] cur = new char[digits.length()];
int curIndex = 0;
backtrace(cur, curIndex, digits, res);
return res;
}
void backtrace(char[] cur, int curIndex, String digits, List<String> res) {
if (curIndex == digits.length()) {
// System.out.println("add res: " + String.valueOf(cur));
res.add(String.valueOf(cur));
return;
}
int d = digits.charAt(curIndex) - '0';
// System.out.println(String.format("cur: %s, curIndex: %d, d: %d", Arrays.toString(cur), curIndex, d));
for (char num : numPad[d]) {
cur[curIndex] = num;
backtrace(cur, curIndex + 1, digits, res);
cur[curIndex] = '\0';
}
}
}
/*
class Solution {
private static char[][] numPad = new char[][]{
new char[]{},
new char[]{},
new char[]{'a', 'b', 'c'},
new char[]{'d', 'e', 'f'},
new char[]{'g', 'h', 'i'},
new char[]{'j', 'k', 'l'},
new char[]{'m', 'n', 'o'},
new char[]{'p', 'q', 'r', 's'},
new char[]{'t', 'u', 'v'},
new char[]{'w', 'x', 'y', 'z'}
};
public List<String> letterCombinations(String digits) {
// System.out.println("numPad: " + Arrays.deepToString(numPad));
LinkedList<String> res = new LinkedList<>();
res.add("");
for (int i = 0; i < digits.length(); i++) {
int d = digits.charAt(i) - '0';
int count = res.size();
while (count-- > 0) {
String tmp = res.removeFirst();
// System.out.println("tmp: " + tmp + ", numPad[d]: " + numPad[d]);
if (numPad[d].length > 0) {
for (char c : numPad[d]) {
res.addLast(tmp + c);
// System.out.println("add: " + tmp + c);
}
} else {
res.addLast(tmp);
}
}
}
if (Objects.equals(res.getFirst(), "")) res.clear();
return res;
}
}
*/
