☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Letter Combinations of a Phone Number

Hard TUF ID 875 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string digits containing digits from 2 to 9. On a classic phone keypad each of these digits carries letters: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz (0 and 1 carry none). Return every string that could be typed by choosing one letter for each digit, in order. If digits is empty, return an empty list, not a list containing the empty string. Any output order is accepted.

The problem is a Cartesian product: the answer is every way of picking one element from each of n small sets, so the size of the answer is the product of the set sizes, between 3^n and 4^n.

Constraints: 0 ≤ digits.length ≤ 4, every character is in '2'..'9'.

Example 1

digits = "23"
answer = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
// 3 letters for 2 times 3 letters for 3 = 9 strings

Example 2

digits = ""
answer = []

Example 3

digits = "9"
answer = ["w", "x", "y", "z"]    // a four-letter key

The letters live in a lookup table indexed by the digit itself, which is shared by all three methods:

static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

Approach 1: Iterative cascade

Intuition. Build the answer digit by digit. Before reading any digit there is exactly one partial string, the empty one. Reading a digit with letters L turns every partial string p into |L| longer strings p + letter. After the last digit the partial strings are complete. This is breadth-first: at each step the whole current list is replaced by the next, larger list. It is easy to reason about and needs no recursion, at the cost of holding every intermediate list in memory and creating a new String object for every extension.

Algorithm.

  1. If digits is empty, return an empty list.
  2. Start with out = [""].
  3. For each digit: create next; for each prefix in out and each letter of the digit, append prefix + letter to next; then set out = next.
  4. Return out.
static List<String> iterative(String digits) {
    List<String> out = new ArrayList<>();
    if (digits.isEmpty()) return out;
    out.add("");                                        // one empty prefix to start from
    for (char ch : digits.toCharArray()) {
        String letters = KEYS[ch - '0'];
        List<String> next = new ArrayList<>(out.size() * letters.length());
        for (String prefix : out) {
            for (char letter : letters.toCharArray()) next.add(prefix + letter);
        }
        out = next;
    }
    return out;
}

Complexity. Time O(4^n · n): the final list has up to 4^n strings of length n, and the total size of the intermediate lists is dominated by the last one (a geometric series). Space O(4^n · n) for the output; the previous level is garbage once replaced.

Approach 2: Optimal, backtracking with a shared StringBuilder

Intuition. Depth-first instead of breadth-first. Level i of the recursion is responsible for digit i: it tries each letter of that digit in turn, appends it to a single shared StringBuilder, recurses to decide the remaining digits, then removes the letter so the next one can be tried. When i reaches the end, the builder holds one complete combination, which we copy out. Only one partial string exists at a time, so the extra memory is the recursion depth n plus the builder, and the only allocations are the 4^n answer strings themselves.

This is the “for-loop recursion” shape of the subsequence pattern with a twist: every level must choose exactly one option (no “not pick” branch), because every digit must be typed.

Algorithm.

  1. If digits is empty, return an empty list.
  2. backtrack(i, cur): if i == digits.length(), add cur.toString() and return.
  3. For each letter of KEYS[digits[i]]: append it, recurse with i + 1, delete the last character.
static List<String> optimal(String digits) {
    List<String> out = new ArrayList<>();
    if (digits.isEmpty()) return out;
    backtrack(digits, 0, new StringBuilder(), out);
    return out;
}

static void backtrack(String digits, int i, StringBuilder cur, List<String> out) {
    if (i == digits.length()) {
        out.add(cur.toString());
        return;
    }
    String letters = KEYS[digits.charAt(i) - '0'];
    for (int j = 0; j < letters.length(); j++) {
        cur.append(letters.charAt(j));
        backtrack(digits, i + 1, cur, out);
        cur.deleteCharAt(cur.length() - 1);             // undo before trying the next letter
    }
}

Dry run on digits = "23":

level i cur before letter tried result
0 ”” a recurse
1 “a” d, e, f record “ad”, “ae”, “af” (undo after each)
0 ”” b recurse
1 “b” d, e, f record “bd”, “be”, “bf”
0 ”” c recurse
1 “c” d, e, f record “cd”, “ce”, “cf”

The output order is lexicographic in the keypad order of letters, the same order the cascade produces.

Complexity. Time O(4^n · n): 4^n leaves each copying an n-character string; the internal nodes are fewer than the leaves. Space O(n) for the recursion stack and the builder, beyond the output.

Approach 3: Mixed-radix decoding

Intuition. Number the combinations from 0 to total - 1, where total is the product of the letter counts. A combination index is then a number written in a mixed radix: the last digit’s position has radix |L_last|, the one before it radix |L_{n-2}|, and so on, like an odometer whose wheels have different numbers of positions. Repeated % radix and / radix extracts the wheel positions from the least significant end, and each position selects a letter. The approach produces the t-th combination directly without visiting any other, which is handy when only some combinations are needed (for example, in pages) or when recursion is unwelcome.

Algorithm.

  1. If digits is empty, return an empty list.
  2. total = Π |KEYS[digit]| over the digits.
  3. For t in 0 .. total - 1: let rest = t; for positions i = n - 1 down to 0, set buf[i] = letters_i[rest % |letters_i|] and rest /= |letters_i|; add new String(buf).
static List<String> mixedRadix(String digits) {
    List<String> out = new ArrayList<>();
    if (digits.isEmpty()) return out;
    int n = digits.length();
    int total = 1;
    for (int i = 0; i < n; i++) total *= KEYS[digits.charAt(i) - '0'].length();
    char[] buf = new char[n];
    for (int t = 0; t < total; t++) {
        int rest = t;
        for (int i = n - 1; i >= 0; i--) {              // the last digit is the least significant position
            String letters = KEYS[digits.charAt(i) - '0'];
            buf[i] = letters.charAt(rest % letters.length());
            rest /= letters.length();
        }
        out.add(new String(buf));
    }
    return out;
}

Decoding t = 100 for "7799" (radices 4, 4, 4, 4): 100 % 4 = 0 → w, 25 % 4 = 1 → x, 6 % 4 = 2 → r, 1 % 4 = 1 → q, giving "qrxw", which is indeed the 101st string the backtracking produces.

Complexity. Time O(4^n · n), n divisions per combination. Space O(n) for the buffer, beyond the output. Because the last digit is treated as least significant, the order matches the other two methods exactly, which the tests rely on.

Edge cases and pitfalls