Difficulty: MediumBacktracking

Letter Combinations of a Phone Number

Problem in Plain English

Given a digit string from 2 to 9, return every letter combination it can spell with the telephone keypad mapping. An empty digit string yields an empty list.

Problem Statement

Given a string digits holding characters from 2 to 9, return every letter string those digits can spell on a classic telephone keypad.

Each digit maps to its letters, for example 2 gives abc and 3 gives def, and each position in the answer takes one letter from its own digit.

Return an empty list when digits is empty; otherwise the answer order does not matter.

Constraints

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

Examples

Example 1

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

Digit 2 offers a, b, c and digit 3 offers d, e, f. Fix a and pair it with d, e, f, then repeat for b and c, giving $3 \times 3 = 9$ distinct two-letter answers.

Example 2

Input: digits = ""
Output: []

The problem explicitly requires no answers when no digits are provided. The internal empty prefix used to start either algorithm is a construction tool, not a result, so return [] rather than [""].

Example 3

Input: digits = "2"
Output: ["a","b","c"]

With only one position, each mapped letter already completes an answer. Digit 2 supplies exactly a, b, c, and there is no second position to extend.

Example 4

Input: digits = "77"
Output: ["pp","pq","pr","ps","qp","qq","qr","qs","rp","rq","rr","rs","sp","sq","sr","ss"]

Both positions independently choose from pqrs, so there are $4 \times 4 = 16$ answers. Repeated digits do not make the positions interchangeable: pq and qp are different strings, while pp is also valid because letters may be reused.

Intuition

Each answer chooses exactly one letter for each digit position. For 23, the first position offers abc and the second offers def, so each of the three first letters pairs with all three second letters. This is a Cartesian product: all combinations of independent position choices. You can build every partial string a layer at a time, or explore one partial string depth-first and undo its last letter before trying a sibling. No branch needs pruning because every choice is valid; the work comes from writing all answers.

Approaches

Level Expansion

Solution Details

Reveal Level Expansion: intuition, complexity, and code

Intuition

Grow the answer one digit at a time: take every string built so far and append each letter of the next digit. Processing the digits left to right in full layers keeps every prefix aligned with its digit.

Step-by-Step Logic

Return [] immediately for empty input. Otherwise start with one empty prefix [""]; in Example 1 the input is 23.
For each digit from left to right, allocate an empty next layer. Append every mapped letter to each current prefix; digit 2 expands the empty prefix into ["a", "b", "c"].
Finish the entire next layer before replacing the current layer. For digit 3, prefix a contributes ad, ae, af, then b contributes bd, be, bf, then c contributes cd, ce, cf.
After the final digit, every prefix has one letter per input position. Return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Why It Works

Before processing any digit, the list contains the one empty prefix. Assume a layer contains exactly all valid prefixes for the digits already processed, each once. Appending every letter of the next digit to every prefix creates only valid longer prefixes and creates every such prefix, since deleting its last letter identifies its unique parent. Different parents or different appended letters cannot produce the same string. Induction over the digits therefore gives exactly all complete combinations once. The empty-input guard enforces the problem's special empty result.

Dry Run

Level Expansion: variable states at each step
digit	current layer	prefix expanded	next layer after expansion
start	`[""]`	none	not allocated
`2`	`[""]`	empty string	`[a,b,c]`
layer commit	`[a,b,c]`	none	next layer released
`3`	`[a,b,c]`	`a` with `d,e,f`	`[ad,ae,af]`
`3`	`[a,b,c]`	`b` with `d,e,f`	`[ad,ae,af,bd,be,bf]`
`3`	`[a,b,c]`	`c` with `d,e,f`	`[ad,ae,af,bd,be,bf,cd,ce,cf]`
layer commit / return	`[ad,ae,af,bd,be,bf,cd,ce,cf]`	no digits left	return `["ad","ae","af","bd","be","bf","cd","ce","cf"]`

Complexity Analysis

Time Complexity

O(n \cdot 4^n)

Space Complexity

O(n \cdot 4^n)

Let n be the nonempty input length and P the product of the mapped letter counts. At depth k, concatenation allocates strings of length k for every prefix. Since each position has at least three choices, the sum of all layer costs is O(nP), bounded by O(n * 4^n) and attained when every digit is 7 or 9. The returned P strings occupy O(nP) characters plus O(P) references. While constructing the final layer, the previous layer remains live with P divided by the last digit's letter count prefixes of length n - 1. Thus auxiliary storage excluding the output is O(nP) in the worst case as well; counting prefixes alone would miss their characters. Empty input takes O(1) time and space. At n = 4, the largest output has 256 strings of four letters.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class Solution {5    public List<String> letterCombinations(String digits) {6        List<String> res = new ArrayList<>();7        if (digits.isEmpty()) return res;8        String[] keys = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};9        // The empty prefix seeds expansion; it is not an answer for empty input.10        res.add("");11        for (char d : digits.toCharArray()) {12            List<String> next = new ArrayList<>();13            for (String prefix : res) {14                for (char ch : keys[d - '0'].toCharArray()) {15                    next.add(prefix + ch);16                }17            }18            // Commit only after expansion, so this digit is appended exactly once.19            res = next;20        }21        return res;22    }23}

Hints

Hint 1

Each answer position draws from exactly one digit, so the answer count is the product of the per-digit letter counts.

Hint 2

Handle one digit per recursion level and loop over that digit's letters inside the level.

Hint 3

Append a letter, recurse to the next digit, then remove the letter; join the buffer into a string only when every digit is consumed.

Edge Cases

Empty input "" has no digits to spell anything, so return an empty list, never a list with one empty string.
A single digit like "7" with four letters returns four one-letter strings ["p", "q", "r", "s"].
Digit "9" maps to four letters wxyz while most digits map to three, which is why the bound uses four to the n.
Repeated digits such as 77 represent independent positions; repeated letters and reversed pairs are valid. The maximum input 7777 returns 256 distinct strings of length four.

Common Mistakes and Interview Tips

Forgetting the empty-input guard and returning a list with one empty string.
Sharing one mutable buffer across answers without copying at the leaf, so every entry ends up spelling the last combination.
Skipping the undo step after recursing, which glues letters from sibling branches into one long string.
Extending the current layer while iterating over it, which can append the same digit repeatedly; build a separate next layer and commit after the loops.
Assuming every digit has three letters drops the fourth choices on 7 and 9. Sorting or deduplicating letters globally also destroys independent position choices.
Interview tip: distinguish O(n) DFS auxiliary space from the O(nP) returned strings, where P is the product of per-digit letter counts. Enumeration cannot avoid writing the output, so DFS improves intermediate storage rather than the output-sized time bound.

Key Takeaway

Per-position choices over a fixed alphabet are a depth-first walk: one buffer, one level per position, and a join at each leaf.