4.18.8 — Letter Combinations of a Phone Number

LeetCode 17 · Medium · ★ Blind 75

The problem

On an old phone keypad, each digit maps to some letters. Given a string of digits from 2 to 9, return every letter combination it could spell.

"23"  →  ["ad","ae","af","bd","be","bf","cd","ce","cf"]
""    →  []

At most 4 digits.

The pattern

The simplest branching in the chapter. The digits are positions, and each digit's letters are the choices at that position.

        ""
    /    |    \          digit '2' → a, b, c
   a     b     c
  /|\   /|\   /|\        digit '3' → d, e, f
 ad ae af ...

No constraints, no pruning, no duplicates. Every leaf is an answer. That makes it the cleanest illustration of the four parts from 4.18.0 with the third part empty.

The size of the answer is the product of the digit letter counts — mostly 3 each, with 7 and 9 giving 4.

The solution

Python

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []                     # the empty input is NOT [""]

        keypad = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
        }

        result = []
        path = []

        def backtrack(i: int):
            if i == len(digits):
                result.append(''.join(path))
                return

            for letter in keypad[digits[i]]:
                path.append(letter)
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

TypeScript

function letterCombinations(digits: string): string[] {
  if (!digits) return [];

  const keypad: Record<string, string> = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
  };

  const result: string[] = [];
  const path: string[] = [];

  function backtrack(i: number): void {
    if (i === digits.length) {
      result.push(path.join(''));
      return;
    }
    for (const letter of keypad[digits[i]]) {
      path.push(letter);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

The empty-input guard is the only trap. Without it, backtrack(0) hits the base case immediately and returns [""] — a list containing one empty string, not an empty list. LeetCode wants [], and this is the test case that fails.

Building a list and joining at the end beats string concatenation. In Python, path + letter on strings allocates a new string at every node; a list plus one join at the leaf does not. It also makes the pop() undo natural.

No constraint check anywhere. Every combination is valid, so the loop has no if. That is what makes this the reference version of the template.

The iterative version

def letterCombinations(self, digits):
    if not digits: return []
    keypad = {...}
    result = ['']
    for d in digits:
        result = [prefix + letter for prefix in result for letter in keypad[d]]
    return result

Start with one empty string, and for each digit replace the whole list with every existing prefix extended by every letter. The list grows by a factor of 3 or 4 per digit.

This is the same doubling structure as the iterative subsets in 4.18.1, and it is arguably the nicer solution here. Write the recursive one in an interview — the question is testing the template — then mention this.

Complexity

O(4^n \times n) where n is the number of digits: at most 4 letters per digit, and O(n) to build each result string.

O(n) space for the recursion, not counting the output.

Since the answer itself has up to 4^n entries, this is optimal.

Where this goes next

• Generate Parentheses — the same shape with a real constraint, which is what turns it from enumeration into pruned search. 4.8.4.
• Combinations of a dictionary, cartesian products, test matrix generation — all this loop.
• Autocomplete on a keypad (T9) — the real use. A phone does not generate all combinations and check each one; it walks a trie of the dictionary in step with the digits, so invalid prefixes die immediately. That is 4.15.3's idea applied here, and it is a good thing to volunteer.

What the interviewer will push on

"What does the empty input return?" [], not [""]. They are checking whether you noticed.

"What is the complexity?" O(4^n \times n), and note that the output size makes it optimal.

"Can you do it iteratively?" The product-building loop.

"How would a real phone do this?" Walk a trie of the dictionary alongside the digits and prune non-words immediately, rather than generating 4^n strings and filtering.

One thing to volunteer: point out that this problem has no constraint step, which is exactly why it is the clearest example of the backtracking template. Then say what changes when a constraint exists — the branch dies before the recursive call.

Next: 4.18.9 N-Queens — the problem backtracking was invented for, where the pruning changes the runtime by four orders of magnitude.