Backtracking — Letter Combinations of a Phone Number
↗ LeetCode: Letter Combinations of a Phone Number · Medium · pattern chapter →
Asked atMetaAmazonGoogleMicrosoftUberBloomberg
Given digits 2-9, return all letter combinations.
Example 1 — digits="23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]Example 2 — digits="" → []
Constraints — 0 ≤ len ≤ 4. Brute nested-loop concat is fine for tiny inputs but scales badly. Backtracking (DFS across digit→letters map) is O(4ⁿ·n) = ~10⁶ ops at n=10 (max phone-number length).
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DFS enumeration (canonical)
java
List<String> letterCombinations(String digits) {
List<String> out = new ArrayList<>();
if (digits.isEmpty()) return out;
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
dfs(digits, 0, map, new StringBuilder(), out);
return out;
}
void dfs(String d, int i, String[] map, StringBuilder sb, List<String> out) {
if (i == d.length()) { out.add(sb.toString()); return; }
for (char c : map[d.charAt(i) - '0'].toCharArray()) {
sb.append(c);
dfs(d, i + 1, map, sb, out);
sb.deleteCharAt(sb.length() - 1);
}
}Execution Trace
Step 1 / 3Initialize scan.
Approach 2 — Iterative BFS
Extend all combinations by next digit's letters; same complexity, no recursion.
Complexity — Time O(4ⁿ · n) worst; Space O(n) recursion.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DFS | O(4ⁿ · n) | O(n) | canonical |
| BFS | O(4ⁿ · n) | O(4ⁿ) | iterative |
When to use which
- Small n → either.
- Very deep → BFS to avoid stack.
- First combination only → early return in DFS.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems