Reference: LeetCode EPI 15.2
Difficulty: Medium

My Post: Java Solution Backtracking with Comments

Problem

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.

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

Example: 

1
2
3
4
5
6
7
8
9
Input: "23"
Output:
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Input: "223"
Output:
["aad","aae","aaf","abd","abe","abf","acd","ace","acf","bad","bae","baf","bbd","bbe","bbf","bcd","bce","bcf","cad","cae","caf","cbd","cbe","cbf","ccd","cce","ccf"]
Extra Output (no duplicate combinations):
["aad","aae","aaf","abd","abe","abf","acd","ace","acf","bbd","bbe","bbf","bcd","bce","bcf","ccd","cce","ccf"]

Follow up: Consider no duplicate combinations.

Analysis

Backtracking

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
// a simple mapping
String[] numToLetters = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

public List<String> letterCombinations(String digits) {
  if (digits.length() == 0) {
    return new ArrayList<>(); // when input = "", returns [] instead of [""]
  }
  List<String> result = new ArrayList<>();
  StringBuilder sb = new StringBuilder();
  combine(0, digits, sb, result);
  return result;
}

private void combine(int d, String digits, StringBuilder sb, List<String> result) {
  if (d >= digits.length()) { // base case
    result.add(sb.toString());
    return;
  }
  
  String selection = numToLetters[digits.charAt(d) - '0'];
  for (int i = 0; i < selection.length(); ++i) {
    char ch = selection.charAt(i); // letter
    sb.append(ch);                 // add
    combine(d + 1, digits, sb, result); // dfs
    sb.setLength(sb.length() - 1); // remove
  }
}

Time: $O(N \times 4^N)$ including string construction with $O(N)$ time at most.
Space: $O(N \times 4^N)$

No Duplicate Combinations

Use the idea of start index in Subsets II. This time we does not pass down the information of whether we pick or do not pick, but the start index as a more general approach.

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
/*
 * Does not allow duplicate combinations
 */
public List<String> letterCombinations(String digits) {
  if (digits.length() == 0) {
    return new ArrayList<>(); // when input = "", returns [] instead of [""]
  }
  List<String> result = new ArrayList<>();
  StringBuilder sb = new StringBuilder();
  combine(0, 0, digits, sb, result);
  return result;
}

private void combine(int d, int startIdx, String digits, StringBuilder sb, List<String> result) {
  if (d >= digits.length()) { // base case
    result.add(sb.toString());
    return;
  }
  
  String selection = numToLetters[digits.charAt(d) - '0'];
  startIdx = (d > 0 && digits.charAt(d - 1) == digits.charAt(d)) ? startIdx : 0;
  for (int i = startIdx; i < selection.length(); ++i) {
    char ch = selection.charAt(i); // letter
    sb.append(ch);                 // add
    combine(d + 1, i, digits, sb, result); // dfs
    sb.setLength(sb.length() - 1); // remove
  }
}

Time: $O(N \times 4^N)$
Space: $O(N \times 4^N)$