Problem statement
Each digit on a phone keypad represents a small group of letters. Given a digit string, build every possible text string by choosing one letter for each digit, in the original order.
For 23, the first position comes from abc and the second from def. The result is not a list of dictionary words: ad and cf are valid even if they are not words.
The public problem statement currently specifies 1–4 digits, each from 2 through 9. The implementation additionally returns an empty list for null/empty input and rejects other characters. Those are defensive behaviors, not additional judge examples.
Constraints & requirements
- CONTRACT
- Public LeetCode statement reviewed 16 October 2026: 1–4 digits, each in 2..9. Mapping: 2=abc, 3=def, 4=ghi, 5=jkl, 6=mno, 7=pqrs, 8=tuv, 9=wxyz. Null/empty returns [] defensively; 0, 1 and other invalid characters are rejected.
Examples 3 test cases
Example 1 Case 1
- Input
digits="23"- Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]
Choose one of abc for digit 2, then one of def for digit 3: 3×3=9 strings.
Example 2 Case 2
- Input
digits="2"- Output
["a","b","c"]
One digit needs one letter, so no two-letter strings belong in this answer.
Example 3 Case 3
- Input
digits="7"- Output
["p","q","r","s"]
Keys 7 and 9 have four letters, not three.
Hints Optional
01Hint 1
Ask what ONE output position needs: exactly one letter from its corresponding digit.
02Hint 2
Let index identify the next digit and path contain choices for digits before index.
03Hint 3
Save a String snapshot only when index reaches the length. After each child, remove the letter you appended.
How to think before coding
Start by asking three small questions:
- What am I building? A string with exactly as many letters as input digits.
- What is one decision? Choose a letter for the current digit, not for any arbitrary digit.
- What remains? Make the same kind of choice for the next digit.
After choosing a for 2, we have reduced the problem to: “Attach every letter for 3 to the prefix a.” The child does not need to reconsider 2. That is the recursive boundary.
If a question asks for every string formed by independent per-position choices, think Cartesian product or backtracking. If it asks whether a word exists in a grid, that is a different problem: positions, adjacency and visited cells matter there.
Brute force and the improvement
One correct but wasteful baseline generates every lowercase string of the required length, then checks whether each letter belongs to the corresponding keypad digit. It explores 26^d candidates for d digits, even though most fail immediately.
Do the validation before branching instead. At digit 2, try only a,b,c; at digit 7, try only p,q,r,s. Every branch now represents a legal prefix, so no completed candidate needs to be filtered out.
This does not remove the unavoidable cost of returning all answers. It removes irrelevant choices. An iterative breadth-by-position product is also valid and has the same output-sensitive running time; DFS keeps only one active prefix rather than a whole frontier of prefixes.
Intuition: the index owns the next position
| State | Meaning |
|---|---|
index |
The next input digit whose letter has not been chosen |
path |
Exactly one letter for every digit before index |
result |
Independent snapshots of completed strings |
At entry, the useful invariant is path.length() == index. It explains both the recursive step and the base case.
Why do we undo if the child returns?
The integer index is local to a frame, but every frame refers to the same mutable StringBuilder. Returning does not delete its last letter.
After the child saves ad, the parent must remove d before appending e. Otherwise the next candidate becomes ade, which is too long and no longer represents one letter per digit.
Why save toString rather than the builder?
The builder keeps changing. path.toString() creates the completed immutable string, so undoing a later choice cannot change ad already stored in the result.
Algorithm
- Store the keypad mapping, including four-letter groups for 7 and 9.
- Begin with
index=0and an empty builder. - If every digit has been processed, save the builder as a String and return.
- Otherwise, append each mapped letter for the current digit in turn.
- Recurse for
index+1, then remove exactly the letter this caller appended. - Continue after every saved answer: the task asks for all combinations.
Java solution
The complete example uses a String array for the mapping. It follows the same choose/recurse/undo idea as the local practice solution, while returning ordinary List<String> results and remaining compatible with Java 17.
import java.util.*;
class Solution {
private static final String[] PHONE_KEYS = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
}; // Array index is the digit; 0 and 1 intentionally have no letters.
public static List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>(); // New result for every invocation.
if (digits == null || digits.isEmpty()) return result; // Defensive empty-input policy.
for (char digit : digits.toCharArray()) {
if (digit < '2' || digit > '9') throw new IllegalArgumentException("Use digits 2..9");
}
buildPhone(digits, 0, new StringBuilder(), result); // No digit has a letter yet.
return result; // All complete strings, not just one successful branch.
}
private static void buildPhone(String digits, int index, StringBuilder path, List<String> result) {
if (index == digits.length()) { // One mapped letter was selected for every digit.
result.add(path.toString()); // Snapshot: later undo must not change a saved answer.
return; // A complete string must not grow beyond the input length.
}
String letters = PHONE_KEYS[digits.charAt(index) - '0']; // Only this digit's legal choices.
for (char letter : letters.toCharArray()) { // Keep other digits' letters out of this position.
path.append(letter); // Choose one letter for the current digit.
buildPhone(digits, index + 1, path, result); // Child fills the next position.
path.deleteCharAt(path.length() - 1); // Restore the parent prefix before the next sibling.
}
}
public static void main(String[] args) {
System.out.println(letterCombinations("23")); // [ad, ae, af, bd, be, bf, cd, ce, cf]
System.out.println(letterCombinations("2")); // [a, b, c]
System.out.println(letterCombinations("7")); // [p, q, r, s]
}
}The main method prints all nine strings for 23, the three letters for 2, then the four letters for 7. The strings are generated in mapping order, but a caller should not depend on answer order unless the task explicitly requires it.
Illustrated dry run
Follow digits="23". The image follows the a subtree in detail and groups the equivalent b and c subtrees; the text transcript identifies the waiting caller and the exact undo operation.

Read the text transcript
Follow the Java, step by step
Example: digits = "23"
What to track: index is local to a frame; path and result are shared. A frame for index i owns one letter at position i. This traces the a branch fully and groups the equivalent b/c branches.
-
Start before digit 2
Java operationbuildPhone(digits, 0, new StringBuilder(), result);Stateindex=0; digit=2; letters=abc; path=""; result=[]No letter is chosen yet. The first loop can choose only a, b or c.
-
Choose a and enter digit 3
Java operationbuildPhone(digits, index + 1, path, result);Statewaiting parent index=0; child index=1; letters=def; path="a"Appending a fills output position 0. Advancing index does not consume any letter choice for digit 3 yet.
-
Choose d and save ad
Java operationresult.add(path.toString());Stateleaf index=2; path="ad"; result=[ad]index equals input length. toString saves immutable text rather than retaining the mutable builder.
-
Undo d and try e, then f
Java operationpath.deleteCharAt(path.length() - 1);Stateindex=1 caller restores "a"; sibling leaves save ae and af; result=[ad,ae,af]Each completed child returns to the same digit-3 loop. Remove only that caller’s appended letter before its next choice.
-
Return to the root and undo a
Java operationpath.deleteCharAt(path.length() - 1);Stateindex=0 caller restores ""; its next letter is bThe digit-3 subtree has finished all three letters. Only now does the root remove its own a.
-
Complete the other root branches
Java operationpath.append(letter);Stateb subtree saves bd,be,bf; c subtree saves cd,ce,cf; final path=""; nine snapshots remainThese sibling subtrees follow exactly the same choose/recurse/undo operations. Enumeration must not stop after ad.
Final result: [ad,ae,af,bd,be,bf,cd,ce,cf]; the shared builder is empty after the search.
To trace the code by hand, write index beside each frame and draw one shared builder separately. When a child returns, move back to the caller’s loop and run the delete operation before its next iteration.
Why it works
Valid prefixes: The root starts empty. Each step adds a letter mapped to exactly the next digit, so the invariant remains true.
Complete answers: The save condition is reached only after all digits have one chosen letter. Every saved string therefore satisfies the contract.
No missing answer: Take any valid output. Its first letter appears in the root’s choices; its second letter appears in that child’s choices, and so on. The search follows that full path.
No duplicate answer: Each letter occurs once within its keypad group. Different choice paths differ at their first different position, so they produce different strings.
Complexity and alternative approaches
Let d be the number of digits and P the product of their group sizes. For 23, P=3×3=9; for 79, P=4×4=16.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Generate all lowercase strings, then validate | O(d × 26^d) | O(d), excluding answers | Correct but explores irrelevant letters |
| Mapped-letter DFS | O(d × P), at most O(d × 4^d) | O(d), excluding answers | One active path; every leaf is valid |
| Iterative product/frontier | O(d × P) | Up to O(d × P) working prefixes | Avoids recursion but stores a broad frontier |
The returned strings themselves occupy O(d × P) space. Copying each length-d answer is real work; reporting only O(P) ignores it. Because every output character must be written, the DFS is output-optimal up to constant factors.
Common mistakes
- Giving 7 or 9 only three letters.
- Treating an empty input as one valid empty answer when your API promises
[]defensively. - Saving the mutable builder instead of a String snapshot.
- Removing the root’s letter before its entire child subtree finishes.
- Returning after the first complete string instead of continuing the sibling loop.
- Claiming constant extra space while ignoring the active recursion frames.