17. Letter Combinations of a Phone Number#
Iterative Approach#
1class Solution {
2
3 public List<String> letterCombinations(String digits) {
4 String[] map = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
5
6 List<String> current = new ArrayList<>();
7 current.add("");
8
9 for (char digit : digits.toCharArray()) {
10 List<String> temp = new ArrayList<>();
11 for (char digitChar : map[digit - '2'].toCharArray()) {
12 for (String c : current) {
13 temp.add(c + digitChar);
14 }
15 }
16 current = temp;
17 }
18
19 return current.size() == 1 ? new ArrayList<String>() : current;
20 }
21}
Recursion Approach 1#
1class Solution {
2
3 private static String[] map = {
4 "abc",
5 "def",
6 "ghi",
7 "jkl",
8 "mno",
9 "pqrs",
10 "tuv",
11 "wxyz",
12 };
13
14 public List<String> letterCombinations(String digits) {
15 if (digits.length() == 0) {
16 return new ArrayList<>();
17 }
18
19 if (digits.length() == 1) {
20 return Arrays.asList(map[digits.charAt(0) - '2'].split(""));
21 }
22
23 List<String> firstCharMap = Arrays.asList(
24 map[digits.charAt(0) - '2'].split("")
25 );
26 List<String> restCharMap = letterCombinations(digits.substring(1));
27
28 List<String> result = new ArrayList<>();
29
30 for (String a : firstCharMap) {
31 for (String b : restCharMap) {
32 result.add(a + b);
33 }
34 }
35
36 return result;
37 }
38}
Recursion Approach 2#
1class Solution {
2
3 private static final Map<Character, String> map = Map.of(
4 '2', "abc",
5 '3', "def",
6 '4', "ghi",
7 '5', "jkl",
8 '6', "mno",
9 '7', "pqrs",
10 '8', "tuv",
11 '9', "wxyz"
12 );
13
14 public List<String> letterCombinations(String digits) {
15 List<String> result = new ArrayList<>();
16
17 if (digits.length() == 0) {
18 return result;
19 }
20
21 combine(digits, 0, "", result);
22 return result;
23 }
24
25 private static void combine(
26 String digits,
27 int index,
28 String current,
29 List<String> result
30 ) {
31 if (index == digits.length()) { // base case
32 result.add(current);
33 return;
34 }
35
36 for (char c : map.get(digits.charAt(index)).toCharArray()) {
37 combine(digits, index + 1, current + c, result);
38 }
39 }
40}
Backtracking Approach#
class Solution {
private static final String[] map = {
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
private List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return result;
}
backtrack(digits, new StringBuilder(), 0);
return result;
}
private void backtrack(String digits, StringBuilder prefix, int index) {
if (prefix.length() == digits.length()) {
result.add(prefix.toString());
return;
}
// - '2' is to offset the map array
for (char c : map[digits.charAt(index) - '2'].toCharArray()) {
prefix.append(c);
backtrack(digits, prefix, index + 1);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}