Letter Combinations of a Phone Number
Problem Statement
Given a string digits containing digits from 2 through 9, return all possible letter combinations that the number could represent. Return the answer in any order. If digits is empty, return an empty list.
Input
A digit string digits where each character maps to letters on a phone keypad.
Output
A list of strings containing every possible letter combination in any order.
Constraints
- •
0 <= digits.length <= 4 - •
digits[i] is a digit from 2 through 9
Examples
Example 1
digits = 23
[ad,ae,af,bd,be,bf,cd,ce,cf]Example 2
digits = empty string
[]Example 3
digits = 7
[p,q,r,s]Learning Objectives
- Recognise digit expansion as a **map each position to several choices** backtracking problem.
- Carry the current digit index and the partially built string as recursion state.
- Use a digit-indexed **String[]** table so each frame can list its candidate letters directly.
- Explain why the output size dominates the runtime for combination generation.
Intuition
Pattern Recognition
This is a map positions to choices problem. Every digit position must be assigned exactly one letter, and the choices for one position are independent of the choices for the other positions. That is a perfect backtracking tree: choose a letter for the current digit, recurse to the next digit, then unchoose so the next sibling letter can be tried.
The state is small: index tells which digit we are filling, and path stores the letters chosen so far. Once index == digits.length, the path has one letter for every digit and is a complete answer. The empty input is the only special case because the platform expects no combinations when there are no positions to fill.
Common mistakes
- ×Returning a list containing an empty string for empty input instead of an empty list.
- ×Using nested loops hard-coded for two or three digits, which fails for variable length input.
- ×Converting digit characters incorrectly by forgetting to subtract **0** before indexing the keypad table.
- ×Appending to a shared builder without deleting the last character after the recursive call.
Algorithm Explanation
State
Each recursion frame carries index, the next digit position to fill, and path, the letters chosen for earlier positions. The keypad mapping is a String[] table where the digit character converts to an integer index. The result stores completed copies of path when all positions are filled.
Recursion tree
For digits = 23, the root is index = 0 with an empty path. Digit 2 branches to a, b, and c. Under the a branch, digit 3 branches to d, e, and f, producing ad, ae, and af at the leaves. The b branch produces bd, be, bf, and the c branch produces cd, ce, cf. Each level corresponds to one digit position, and every root-to-leaf path is one output string.
Pruning
There is no value-based pruning because every letter choice for a valid digit can lead to an answer. The structural pruning is the base case: stop exactly when index == digits.length and copy the current path. For empty input, return immediately before starting DFS so the result is [].
Algorithm
- Build a keypad table whose entries for digits 2 through 9 contain their letters.
- If digits is empty, return an empty result list.
- Start DFS at index = 0 with an empty StringBuilder path.
- Read the letters for digits[index].
- For each candidate letter, append it to path and recurse with index + 1.
- When the recursive call returns, delete the last character to unchoose that letter.
- When index == digits.length, add path.toString() to the result.
Solutions
Solution: Digit-index DFS with keypad table
Use a digit-indexed table to fetch the candidate letters in O(1). The DFS fills one position at a time, so the recursion depth equals the number of digits and each leaf contributes one output string.
Step-by-step
- Create the result list and return it immediately for empty digits.
- Store keypad letters in a String[] table indexed by the numeric digit value.
- In the helper, if index has reached the input length, append the built string to the result.
- Otherwise, iterate through the letters for the current digit.
- Append one letter, recurse to the next digit, then delete that letter before trying the next candidate.
O(4^n * n)
O(n)
There are at most 4 choices per digit and copying each completed string costs up to n. Auxiliary recursion and builder space are O(n), excluding output.
Java implementation
Dry Run
Sample input
digits = 23. Track the digit index, the letter choice, and the mutable path as DFS moves down and back up the tree.
| depth | start | choice | path | action |
|---|---|---|---|---|
| 0 | 0 | digit 2 -> a | a | choose a and recurse to index 1 |
| 1 | 1 | digit 3 -> d | ad | choose d, next index reaches the base case |
| 2 | 2 | complete | ad | copy ad to result |
| 1 | 1 | unchoose d, choose e | ae | copy ae after the base case |
| 1 | 1 | unchoose e, choose f | af | copy af after the base case |
| 0 | 0 | unchoose a, choose b | b | explore the b branch against digit 3 |
| 1 | 1 | digit 3 -> d | bd | copy bd after the base case |
| 0 | 0 | unchoose b, choose c | c | explore the c branch against digit 3 |
| 1 | 1 | digit 3 -> f | cf | last leaf in this sample branch |
The full DFS produces 3 branches for digit 2 and 3 branches under each of them for digit 3, giving 3 * 3 = 9 combinations.
Interview Tips
Lead with the position-to-choices model: one digit position is filled per recursion level. Mention that a StringBuilder avoids creating a new string at every internal node, but completed answers still must be copied into result strings. Be explicit about the empty input behavior because it is a common edge case in this problem.
Likely follow-ups
- How would the solution change if digits **0** and **1** had custom letter mappings?
- How would you stream combinations one at a time instead of storing them all?
- How would you count combinations without materializing the strings?
- How would you support a keypad where each digit has a variable number of letters loaded at runtime?
Similar Problems
Key Takeaways
- When each input position maps to a small set of choices, use one recursion level per position.
- A keypad table keeps digit-to-letter lookup simple and avoids conditional chains.
- The base case records a string only after every digit has been assigned.
- The exponential runtime is unavoidable because the output itself is exponential.