Letter Combinations of a Phone Number
Problem
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent by mapping digits to letters on a phone keypad.
- 0 ≤ digits.length ≤ 4
- digits[i] is a digit in the range ['2', '9']
Example
digits = "23"["ad","ae","af","bd","be","bf","cd","ce","cf"]Starting with digits "23", the algorithm explores all letter combinations by mapping '2' to 'abc' and '3' to 'def'. It begins with an empty string and appends each letter from 'abc' for the first digit, then recursively appends each letter from 'def' for the second digit. The critical moment is when the current combination length equals the digits length, at which point the combination is added to the result list. This exhaustive exploration ensures all valid combinations are generated.
Approach
Straightforward Solution
A brute-force approach would generate all possible letter combinations by nested loops for each digit, which is feasible for small input but not scalable or elegant. This approach quickly becomes cumbersome as the number of digits grows.
Core Observation
Each digit maps to a set of letters, and the problem asks for all possible strings formed by choosing one letter per digit in order. This naturally forms a tree of choices where each level corresponds to a digit and branches correspond to letters.
Path to Optimal
PreviewRecognizing the problem as a combinatorial search over a fixed set of choices per digit leads to backtracking. Backtracking systematically explores all possible letter sequences by recursively choosing letters for each digit and backtracking after exploring each path…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a recursive backtracking function that tracks the current index in the digits string and the current combination string. At each recursion level, iterate over the letters mapped to the current digit, append one letter to the current combination, and recurse to the next digit…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(3^n * 4^m)
Each digit maps to 3 or 4 letters. For n digits mapping to 3 letters and m digits mapping to 4 letters, the total number of combinations is 3^n * 4^m. The algorithm explores all these combinations exactly once.
Space
O(n)
The recursion stack depth is at most n (length of digits), and the current combination string uses O(n) space. The output list size is not counted as auxiliary space.
Pattern Spotlight
Backtracking (State Restoration)
For problems requiring all combinations or permutations, use a recursive 'choose, explore, un-choose' pattern that builds partial solutions step-by-step and backtracks to explore alternative branches, ensuring exhaustive and non-redundant search.
Solution
| 1 | class Solution:
|
| 2 | def letterCombinations(self, digits: str) -> list[str]:
|
| 3 | res = []
|
| 4 | digit_to_char = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
|
| 5 | "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" }
|
| 6 |
|
| 7 | def backtrack(i, cur_str):
|
| 8 | if len(cur_str) == len(digits):
|
| 9 | res.append(cur_str)
|
| 10 | return
|
| 11 |
|
| 12 | for c in digit_to_char[digits[i]]:
|
| 13 | backtrack(i + 1, cur_str + c)
|
| 14 |
|
| 15 | if digits:
|
| 16 | backtrack(0, "")
|
| 17 |
|
| 18 | return res |
Step-by-Step Solution
Map Digits to Letters and Initialize Result Storage
| 3 | res = []
|
| 4 | digit_to_char = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
|
| 5 | "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" }
|
Objective
To establish the digit-to-letter mapping and prepare a list to accumulate all valid letter combinations.
Key Insight
The digit-to-letter mapping is fixed and known, so storing it in a dictionary allows constant-time lookup of possible letters for each digit. Initializing the result list upfront provides a container to collect all valid combinations generated by backtracking.
Interview Quick-Check
Core Logic
Using a dictionary for digit-to-letter mapping enables efficient retrieval of candidate letters for each digit during recursion.
State & Boundaries
Initializing an empty result list before recursion ensures all valid combinations can be collected and returned after exploration.
Recursively Explore Letter Combinations via Backtracking
To systematically build all letter combinations by recursively choosing letters for each digit and backtracking after exploring each path.
Trigger Backtracking Only for Non-Empty Input and Return Results
To initiate the backtracking process only if the input digits string is non-empty and return the accumulated results.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if len(cur_str) == len(digits):Check if the current combination length equals the digits length.
This base case identifies when a complete letter combination has been formed, signaling that it should be added to the results.
backtrack(i + 1, cur_str + c)Recursively call backtracking with next index and updated combination string.
Advancing the index and extending the combination string explores deeper levels of the decision tree, building complete combinations step-by-step.
Full line-by-line criticality + rationale for all 12 lines available on Pro.
Test Your Understanding
Why is backtracking the appropriate approach for generating all letter combinations instead of iterative nested loops?
See the answer with Pro.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Letter Combinations of a Phone Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Letter Combinations of a Phone Number drill