Letter Combinations of a Phone Number

PracticeNeetCode ↗LeetCode ↗

Given a string of digits from 2–9, return every possible letter combination the number could represent on a standard phone keypad, in any order.

Example

Key Pointers

• Each digit maps to a fixed 3–4 letters via a lookup table — the recursion just picks one letter per digit position, in order.
• Empty input should return an empty list, not a list containing an empty string — worth checking explicitly before recursing.
• Recursion depth equals the number of digits; the branching factor at each level is the number of letters that digit maps to.

Step-by-Step Analysis

1. If digits is empty, return [].
2. Build a digit → letters lookup table ("2": "abc", "3": "def", and so on).
3. Define backtrack(index): if index == len(digits), record "".join(path).
4. Otherwise loop over every letter mapped to digits[index]: append the letter, recurse with backtrack(index + 1), then pop.
5. Call backtrack(0) and return the result.

Complexity

Time: O(4ⁿ · n) — Space: O(n) recursion depth

Code

def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []

    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    result = []
    path = []

    def backtrack(index: int) -> None:
        if index == len(digits):
            result.append("".join(path))
            return
        for letter in mapping[digits[index]]:
            path.append(letter)
            backtrack(index + 1)
            path.pop()

    backtrack(0)
    return result

Code Explanation

How the solution above works, piece by piece.

1. An empty input returns an empty list (not [""]).
2. mapping gives each digit's letters, as on a phone keypad.
3. backtrack(index) chooses a letter for digits[index]. When every digit has a letter, join path into a string.
4. Loop over that digit's letters: append, recurse to the next digit, pop.
5. Up to 4ⁿ combinations (7 and 9 have four letters), each built in O(n): O(n · 4ⁿ).

Visual Walkthrough

The recursion tree for digits = "23":

Video Explanation

NeetCode — Backtracking, LeetCode 17