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);
    }
  }
}