1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
// back tracking
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return new ArrayList<String>();
List<String> ret = new LinkedList<String>();
backtrack("", digits, 0, ret);
return ret;
}
private void backtrack(String prefix, String digits, int offset, List<String> ret) {
if (offset >= digits.length()) {
ret.add(prefix);
return;
}
String letters = KEYS[(digits.charAt(offset) - '0')];
for (int i = 0; i < letters.length(); i++) {
backtrack(prefix + letters.charAt(i), digits, offset + 1, ret);
}
}
/*
Iterative solution. For each digit added, remove and copy every element in the queue and add the possible letter to each element, then add the updated elements back into queue again. Repeat this procedure until all the digits are iterated.
*/
public List<String> letterCombinationsItr(String digits) {
List<String> list = new ArrayList<>();
if (digits == null || digits.length() == 0) return list;
LinkedList<String> res = new LinkedList<String>(); // use a queue
String[] mapping = new String[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
res.add("");
for (int i = 0; i < digits.length(); i++) {
int x = Character.getNumericValue(digits.charAt(i));
while (res.peek().length() == i) {
String t = res.remove();
for (char s : mapping[x].toCharArray()) {
res.add(t + s);
}
}
}
return res;
}
|
**Input:**Digit string “23”Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].