Letter Combinations of a Phone Number

On an old phone keypad, each key from 2 to 9 is printed with a few letters:

• 2: abc, 3: def, 4: ghi, 5: jkl
• 6: mno, 7: pqrs, 8: tuv, 9: wxyz

You are given a string digits made of the characters 2 to 9. Return every string that can be typed by choosing one letter for each digit, keeping the digits in their original order. The answer may be returned in any order. If digits is empty, return an empty list.

Example 1

Example 2

Example 3

Constraints

• 0 <= digits.length <= 4
• digits[i] is a character from '2' to '9'

Pattern Path · Backtracking · problem 122 of 169

Start simple

Generate every string of n letters from a to z and keep those whose letters sit on the right keys: O(n·26ⁿ) time, versus O(n·4ⁿ) for direct enumeration.

The key idea

The answer is the Cartesian product of the letter groups of each digit, so the job is to enumerate that product without missing or repeating anything. Backtracking does exactly that: walk the digits left to right, and at each position try every letter the key offers, appending it to a shared prefix.

When the prefix length equals the number of digits, every position has been decided, so the prefix is one complete combination and is saved. After a recursive call returns, the letter is removed (or simply not kept, if you pass a new string down), which lets the next letter take its place. Because each level branches over a fixed set of letters and the levels follow the digit order, every combination is reached exactly once.

The empty input needs care: with no digits there are no keys to press, so the expected result is [], not [""]. A guard at the start handles it.

An iterative version is equally good: start from [""] and, for each digit, replace the list with every existing prefix extended by every letter of that digit.

Complexity

• Time: O(n · 4^n)
• Space: O(n) besides the output

Python

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        keypad = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
        }
        result = []

        def build(index, prefix):
            if index == len(digits):
                result.append(prefix)
                return
            for letter in keypad[digits[index]]:
                build(index + 1, prefix + letter)

        build(0, "")
        return result

JavaScript

var letterCombinations = function(digits) {
  if (digits.length === 0) return [];
  const keypad = {
    2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl',
    6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz',
  };
  const result = [];
  const build = (index, prefix) => {
    if (index === digits.length) {
      result.push(prefix);
      return;
    }
    for (const letter of keypad[digits[index]]) {
      build(index + 1, prefix + letter);
    }
  };
  build(0, '');
  return result;
};

What the interviewer is checking

This checks whether you can write a clean recursive enumeration with a clear base case, and whether you can state why the running time is exponential and unavoidable.

Mistakes to avoid

• Returning [""] instead of [] for an empty input.
• Forgetting that 7 and 9 have four letters, not three.
• Building strings with repeated concatenation inside deep loops in a way that copies a lot more than needed (fine at this size, but worth mentioning).

Follow-ups to expect

• Can you do it without recursion? (Grow a list of prefixes digit by digit.)
• What if you only need the k-th combination? (Mixed-radix counting over key sizes.)
• What if only dictionary words should be returned? (Prune prefixes with a trie.)

In real software

T9 predictive text on early phones mapped digit sequences to candidate words this way, and vanity phone numbers are still checked against the same letter groups.

Practice next