17. Letter Combinations of a Phone Number

MediumBacktrackingBacktracking over a fixed keypad mappingCartesian product of digit-letter groups

Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9, return all possible letter combinations that the number could spell on a classic phone keypad. Return the combinations in any order. An empty input string yields an empty list.

Open official problem prompt ↗

In plain English

Enumerate every string obtainable by replacing each digit with one of its keypad letters, one letter per digit.

Picture it like this

Old T9 texting: each number key hides several letters, and you want to list every word-shape you could type if you tapped each key once and picked any of its letters.

Example

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Why: Digit 2 maps to {a,b,c} and 3 maps to {d,e,f}; every pairing of one letter from each gives 3 x 3 = 9 strings.

Constraints

0 <= digits.length <= 4digits[i] is a digit in the range ['2', '9']

Pattern lesson

See the pattern, then code

Cartesian product of digit-letter groups

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Process digits left to right. At depth i, branch once per letter that digits[i] maps to, appending it to the running string; when the string reaches the length of digits, it is one complete combination.

New words, made simpleKnow these before the algorithm

Cartesian product: All ordered tuples formed by taking one element from each of several sets.
Keypad mapping: The fixed dictionary from each digit 2-9 to its group of letters.
Depth = index: Recursion depth equals the digit position currently being assigned a letter.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Iterative queue expansion

Correct and loop-based, but holds all partial strings in memory at once; slightly more bookkeeping.

Start with [''] and for each digit replace the queue with every existing prefix extended by each mapped letter.

Time O(4^n * n)Space O(4^n * n)

Best choiceBacktracking (DFS)

Minimal extra memory beyond the path and recursion stack; the clearest expression of the product structure.

Recurse digit by digit, appending one mapped letter per level and recording on completion.

Time O(4^n * n)Space O(n)

The rule we keep true

Invariant

At the call for index i, path holds exactly i chosen letters, one for each digit processed so far, in order.

Why this is correct

Reasoning

Every leaf of the tree is reached by choosing one letter at each digit, which is precisely one element of the Cartesian product; because each digit's loop covers all its letters and depth advances by one per digit, every product tuple is produced once and only once.

The algorithm in three movesSay these aloud before coding

1Return [] immediately if digits is empty

i=0 pick 'a'

2Build the digit -> letters mapping

i=1 pick 'd' -> record 'ad'

3Recurse over digit index i, trying each mapped letter; when i equals len(digits), record the assembled string

backtrack -> 'ae', 'af', ...

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

2->abc0

3->def1

1 · Readdigits='23'

2 · AskEmpty input?

3 · Update stateres=[]

4 · ResultNot empty; proceed to backtrack(0)

Key takeaway

A two-level tree: three branches for digit 2, each splitting into three for digit 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Empty guard
An empty digits string has zero combinations, so return [] before doing any work.
2
Lines 5-8Keypad mapping
A dictionary encodes the fixed digit-to-letters relationship used at each level.
3
Lines 13-19Per-digit branching
At index i, loop over every mapped letter, push it, recurse to the next digit, then pop; when i hits the end, join path into a finished string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty string returns [] (not [''])
Single digit like '7' returns all four of p,q,r,s
Digits containing 7 or 9 branch four ways, raising the count

Common beginner mistakes

Returning [''] instead of [] for empty input
Hardcoding three letters per digit and mishandling 7 (pqrs) and 9 (wxyz)
Building strings by concatenation in a way that mutates shared state without restoring it

Check your understanding

Why is the empty-input case handled specially rather than falling out of the recursion?

PyPython 3 · solution.py

Optimal

1class Solution:2    def letterCombinations(self, digits: str) -> list[str]:3        if not digits:4            return []5        mapping = {6            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',7            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',8        }9        res: list[str] = []10        path: list[str] = []1112        def backtrack(i: int) -> None:13            if i == len(digits):14                res.append(''.join(path))15                return16            for ch in mapping[digits[i]]:17                path.append(ch)18                backtrack(i + 1)19                path.pop()2021        backtrack(0)22        return res

Time complexityO(4^n * n) where n = len(digits)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMetaUber

Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking