Letter Combinations of a Phone Number (LeetCode 17)

The problem

On an old phone keypad, each digit from 2 to 9 maps to a few letters: 2 → abc, 3 → def, …, 7 → pqrs, 9 → wxyz. Given a string of such digits, return every letter string it could spell. If the input is empty, return an empty list.

Input:  digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

2 gives three letters and 3 gives three, so there are 3 × 3 = 9 combinations.

How to think about it

Start with brute force. For a fixed length you could write nested loops: two digits, two loops. But the number of digits isn’t known in advance, so you can’t write the right number of loops by hand. That is the real problem to solve.

The key insight: recursion is a variable number of nested loops. Let the recursion depth stand for “which digit am I on”. At depth i, loop over the letters of digits[i], and for each letter go one level deeper. When i reaches the end of the string, the path is a complete word. The tree has one level per digit and three or four branches per node.

No pruning, no duplicates. Every leaf is a valid answer, and every path is unique because each level picks from a different digit. So there is nothing to skip. This is the simplest shape backtracking takes, and it’s a good warm-up before problems with constraints.

Which pattern is this? Backtracking over a product of choices. The tell is “all combinations, where position i has its own set of options”. Building path + ch creates a new string each time, so there’s no explicit undo.

Approach

1. If digits is empty, return [] (not [""]).
2. Keep a map from each digit to its letters.
3. bt(i, path): if i == len(digits), record path and return.
4. Otherwise, for each letter of digits[i], call bt(i + 1, path + letter).
5. Start with bt(0, '').

Solution

def letter_combinations(digits):
    if not digits: return []                 # empty input means no combinations
    m = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    res = []
    def bt(i, path):
        if i == len(digits): res.append(path); return   # one letter per digit: done
        for ch in m[digits[i]]: bt(i + 1, path + ch)    # branch on each letter
    bt(0, ''); return res
# letter_combinations("23") -> ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Dry run

On digits = "23":

Nine leaves, nine words.

Complexity

• Time: O(4ⁿ · n) for n digits. In the worst case every digit is 7 or 9 (four letters), giving 4ⁿ leaves, and building each string costs O(n).
• Space: O(n) for the recursion depth, not counting the output.

Edge cases and pitfalls

• Empty input must return []. Without the first line, the recursion would immediately record '' and return [""], which LeetCode marks wrong.
• Digits 7 and 9 have four letters. Don’t hard-code three branches.
• Digits 0 and 1 map to nothing. LeetCode doesn’t include them, but a lookup would raise KeyError if they appeared.
• An iterative version also works: start with [""] and, for each digit, extend every partial string with each letter.

Related problems

• Generate Parentheses (LeetCode 22): build-a-string backtracking, with pruning added.
• Combinations (LeetCode 77): a fixed-depth tree where each level picks a number.
• Word Search (LeetCode 79): one recursion level per character, on a grid.