BFS using queue: LinkedList1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public List<String> letterCombinations(String digits) {
LinkedList<String> ans = new LinkedList<String>();
if (digits.isEmpty()) return ans;
String[] map = new String[] { "0", "1",
"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
ans.add("");
while (ans.peek().length() != digits.length()) {
String prefix = ans.poll();
String letters = map[digits.charAt(prefix.length()) - '0'];
for (char ch : letters.toCharArray()) {
ans.offer(prefix + ch);
}
}
return ans;
}
}
BackTracking, Time complexity : O(3^N * 4^M)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
37class Solution {
Map<String, String> phone_num = new HashMap<String, 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");
}
};
List<String> output = new ArrayList<String>();
StringBuilder newstr = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return new ArrayList<>();
backtrack(digits);
return output;
}
public void backtrack(String next_digits) {
if (next_digits.length() == 0) {
output.add(newstr.toString());
return;
} else {
String digit = next_digits.substring(0, 1);
String letters = phone_num.get(digit);
for (int i = 0; i < letters.length(); i++) {
newstr.append(letters.substring(i, i + 1));
backtrack(next_digits.substring(1));
newstr.deleteCharAt(newstr.length() - 1);
}
}
}
}