Letter Combinations of a Phone Number

Problem

On an old phone keypad each digit from 2 to 9 maps to a group of letters: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz (1 and 0 map to nothing). Given a string digits containing only characters 2–9, return every string that can be formed by picking one letter for each digit, in the digits’ order. Return them in any order. If digits is empty, return an empty list.

Examples

• digits = "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"] — 3 letters for 2 × 3 letters for 3 = 9 strings.
• digits = "" → [] — no digits means no combinations (not [""]).
• digits = "7" → ["p","q","r","s"] — a single 4-letter digit.

Constraints

• 0 <= len(digits) <= 4
• digits[i] is a character in '2'..'9'

With at most 4 digits and at most 4 letters per digit, the output holds at most 4^4 = 256 strings. The output size equals the running time, so every correct algorithm is asymptotically optimal; the exercise is generating the combinations cleanly.

Think about it first

TL;DR

DFS backtracking over one letter per digit — O(4^n · n) time, O(n) space beyond the output (n = number of digits).

Approach 1 — Brute force: iterative prefix expansion

The output has up to 4^n strings, so every correct algorithm pays at least O(4^n · n) just to produce it. A straightforward starting point is breadth-first expansion: keep the list of all prefixes built so far, and for each new digit, replace the list with every prefix extended by every letter of that digit.

from typing import List

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


def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []
    prefixes = [""]
    for d in digits:
        letters = KEYPAD[d]
        prefixes = [p + ch for p in prefixes for ch in letters]
    return prefixes

Walkthrough on digits = "23":

Complexity: O(4^n · n) time (each of ≤ 4^n final strings is built through n concatenations), O(4^n · n) working space since every intermediate generation is materialized. This is acceptable under the constraints, but it holds all prefixes in memory at once. The DFS version below cuts the working space to O(n).

Approach 2 — Backtracking (DFS on the digit index)

The insight: the answers are the leaves of a tree whose level i branches once per letter of digits[i], so a depth-first traversal that carries the current path visits every leaf while storing only one partial string at a time. This is backtracking: extend the partial solution by one choice, recurse, then undo the choice and try the next.

For digits = "23" the tree has nine leaves, one per output string:

flowchart TD
    root([""""]) --> a["a"]
    root --> b["b"]
    root --> c["c"]
    a --> ad["ad"]
    a --> ae["ae"]
    a --> af["af"]
    b --> bd["bd"]
    b --> be["be"]
    b --> bf["bf"]
    c --> cd["cd"]
    c --> ce["ce"]
    c --> cf["cf"]

from typing import List

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


def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []
    result: List[str] = []
    path: List[str] = []

    def backtrack(i: int) -> None:
        if i == len(digits):
            result.append("".join(path))
            return
        letters = KEYPAD[digits[i]]
        for ch in letters:
            path.append(ch)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Walkthrough on digits = "23":

• i=0, pick a → i=1, pick d → i=2 → record "ad", pop d; pick e → "ae", pop; pick f → "af", pop; pop a.
• Pick b → same inner loop → "bd", "be", "bf".
• Pick c → "cd", "ce", "cf".

Nine leaves, visited in dictionary order, with never more than 2 characters of working path in memory.

Complexity: O(4^n · n) time (4 is the largest letter group, the join costs n per leaf); O(n) extra space for path and recursion — the advantage over Approach 1’s O(4^n · n) working set.

Approach 3 — Library cross product

The insight: “one letter per digit, all ways” is the Cartesian product of the letter groups, which Python provides as itertools.product. It performs the same enumeration internally. In an interview, mention it, then implement Approach 2 by hand.

from itertools import product
from typing import List

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


def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []
    groups = [KEYPAD[d] for d in digits]
    return ["".join(combo) for combo in product(*groups)]

Walkthrough on digits = "7": groups = ["pqrs"], and the product of a single group is its letters one at a time → ["p","q","r","s"].

Complexity: O(4^n · n) time, O(n) space beyond the output (product yields tuples lazily).

Common pitfalls

• Returning [""] instead of [] for empty input — the empty product technically has one element, but the problem wants an empty list; guard if not digits first.
• Building the path by string concatenation into the recursive call (backtrack(i + 1, s + ch)) is fine at n ≤ 4 but copies the whole prefix at every level; the append/pop list idiom avoids the copies.
• Forgetting that 7 and 9 map to four letters — hardcoding 3 breaks half the keypad.
• Mapping 1 or 0 to letters — the constraints exclude them, but a defensive KEYPAD lookup would raise a KeyError rather than silently produce wrong output, which is what you want.

Pattern takeaway

This is backtracking with no pruning: a pure enumeration where the recursion tree is the answer set. When each position has an independent set of options and you need every full selection, DFS with append/recurse/pop generates the cross product in O(depth) working memory. The same skeleton reappears, with pruning added, in constraint problems such as N-Queens and Sudoku, so this version is worth knowing cold.