Leetcode 17. Letter Combinations of a Phone Number
Given a string of digits 2–9, return all possible letter strings by mapping each digit to its phone-keypad letters — effectively computing the Cartesian product of per-digit letter sets; this is typically solved by DFS/backtracking to enumerate combinations (digits length ≤ 4).
DESCRIPTION
Given a string of digits 2–9, return all possible letter strings by mapping each digit to its phone-keypad letters — effectively computing the Cartesian product of per-digit letter sets; this is typically solved by DFS/backtracking to enumerate combinations (digits length ≤ 4).
Input:
digits = "23"
Output:
["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: Digit '2' maps to ['a','b','c'] and digit '3' maps to ['d','e','f']. All 9 combinations (3×3) are generated by pairing each letter from '2' with each letter from '3'
Constraints:
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9']
- Phone keypad mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz
Understanding the Problem
Let's understand what we're being asked to do. We have a string of digits like '23' and need to generate all possible letter combinations based on phone keypad mappings.
Tracing through '23': digit '2' maps to letters ['a','b','c'] and digit '3' maps to ['d','e','f']. We need all combinations: 'ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf' - that's 9 total combinations (3 × 3).
Important constraint: Each digit maps to 3-4 letters (digit '7' and '9' have 4 letters each). The input string length is at most 4, so we won't have an explosion of combinations.
Edge cases to consider: What if the input is empty? (return empty list). What if input has only one digit? (return all letters for that digit). The problem guarantees digits are only 2-9, so no need to handle '0' or '1'.
Building Intuition
For each digit in the input, we need to choose one letter from its mapping. If we have 2 digits, we make 2 choices. If we have 3 digits, we make 3 choices.
This is a decision tree where at each level, we branch into multiple possibilities (one branch per letter option). Each path from root to leaf represents one valid combination.
By exploring all possible paths through this decision tree, we systematically generate every combination without missing any or creating duplicates.
The total number of combinations is the product of the number of letters for each digit. For '23': 3 letters × 3 letters = 9 combinations. For '234': 3 × 3 × 3 = 27 combinations.
Think of building a combination step-by-step, like filling in blanks: _ _ _ for input '234'.
For the first blank, try 'a' (from digit '2'), then recursively fill the remaining blanks. When you've filled all blanks, you have one complete combination. Then backtrack - undo the last choice and try the next option ('b', then 'c'). This explore-and-backtrack pattern naturally generates all combinations.
Common Mistakes
Forgetting to backtrack: After exploring one branch, you must remove the last added letter before trying the next option. Without backtracking, you'll build incorrect combinations like 'abc' instead of separate 'a', 'b', 'c' paths.
Not handling empty input: The edge case of empty string should return an empty list, not a list containing an empty string. Check for this before starting recursion.
Incorrect base case: The recursion should stop when current combination length equals digits length, not when you've processed all letters. The base case is about the combination being complete, not about exhausting options.
Inefficient string concatenation: In languages like Java, repeatedly concatenating strings creates new objects. Use StringBuilder or pass indices instead of building strings at each step.
Off-by-one errors in indexing: Make sure the current digit index matches the current combination length. If you're building combination 'ad', you should be processing digits[2] next, not digits[1].
Optimal Solution
Use depth-first search with backtracking to explore all possible letter combinations. Start with an empty string and recursively add one letter at a time from each digit's mapping. When the current combination length equals the input digits length, we've found a complete combination - add it to results. Then backtrack by removing the last letter and trying the next option. This systematically explores the entire decision tree of letter choices.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(4^n × n) In the worst case (all digits are 7 or 9), each digit has 4 letter choices, giving 4^n combinations where n is the input length. For each combination, we spend O(n) time building the string. Since n ≤ 4, this is effectively O(4^4) = O(256) combinations maximum.
Space Complexity: O(n) The recursion depth is at most n (one level per digit), and we store the current combination string of length n. The output list size is not counted in auxiliary space complexity.
What We've Learned
- backtracking mastery: Understanding when and why to use backtracking data structure for this type of problem pattern
- Algorithm optimization: Recognizing how to achieve O(4^n × n) time complexity through efficient problem decomposition
- Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
- Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
- Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice
Related Concepts and Problems to Practice
Subsets is a classic backtracking problem that generates all possible combinations from a set, similar to how Letter Combinations generates all possible strings from digit-to-letter mappings. Both problems use DFS/backtracking to explore the solution space and build combinations incrementally.
Generate Parentheses uses backtracking to build valid strings character-by-character with constraints, very similar to Letter Combinations which builds strings by choosing letters for each digit. Both problems demonstrate the pattern of making choices at each step and exploring all valid combinations through recursive backtracking.
Test Your Understanding
Why is backtracking the right data structure for this problem?
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late July, 2026
Early February, 2026
Mid December, 2025
Hello Interview Premium
Your account is free and you can post anonymously if you choose.