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
Recognizing 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. This approach elegantly handles variable input length and avoids redundant computations.
Optimal Approach
Use 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. When the current combination length equals the digits length, add it to the result list. This approach explores all valid combinations efficiently and cleanly.
Time
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 |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.List; |
| 3 | import java.util.Map; |
| 4 | |
| 5 | public class Solution { |
| 6 | public List<String> letterCombinations(String digits) { |
| 7 | List<String> res = new ArrayList<>(); |
| 8 | Map<Character, String> digitToChar = Map.of( |
| 9 | '2', "abc", |
| 10 | '3', "def", |
| 11 | '4', "ghi", |
| 12 | '5', "jkl", |
| 13 | '6', "mno", |
| 14 | '7', "pqrs", |
| 15 | '8', "tuv", |
| 16 | '9', "wxyz" |
| 17 | ); |
| 18 | |
| 19 | if (digits == null || digits.isEmpty()) { |
| 20 | return res; |
| 21 | } |
| 22 | |
| 23 | backtrack(digits, 0, "", res, digitToChar); |
| 24 | return res; |
| 25 | } |
| 26 | |
| 27 | private void backtrack(String digits, int i, String curStr, List<String> res, Map<Character, String> digitToChar) { |
| 28 | if (curStr.length() == digits.length()) { |
| 29 | res.add(curStr); |
| 30 | return; |
| 31 | } |
| 32 | |
| 33 | for (char c : digitToChar.get(digits.charAt(i)).toCharArray()) { |
| 34 | backtrack(digits, i + 1, curStr + c, res, digitToChar); |
| 35 | } |
| 36 | } |
| 37 | } |
| 1 | #include <string> |
| 2 | #include <vector> |
| 3 | #include <unordered_map> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | vector<string> letterCombinations(string digits) { |
| 10 | vector<string> res; |
| 11 | unordered_map<char, string> digitToChar = { |
| 12 | {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, |
| 13 | {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} |
| 14 | }; |
| 15 | |
| 16 | if (digits.empty()) { |
| 17 | return res; |
| 18 | } |
| 19 | |
| 20 | backtrack(digits, 0, "", res, digitToChar); |
| 21 | return res; |
| 22 | } |
| 23 | |
| 24 | private: |
| 25 | void backtrack(const string& digits, int i, string curStr, vector<string>& res, const unordered_map<char, string>& digitToChar) { |
| 26 | if (curStr.length() == digits.length()) { |
| 27 | res.push_back(curStr); |
| 28 | return; |
| 29 | } |
| 30 | |
| 31 | for (char c : digitToChar.at(digits[i])) { |
| 32 | backtrack(digits, i + 1, curStr + c, res, digitToChar); |
| 33 | } |
| 34 | } |
| 35 | }; |
| 1 | var letterCombinations = function(digits) { |
| 2 | const res = []; |
| 3 | const digitToChar = { |
| 4 | '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', |
| 5 | '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' |
| 6 | }; |
| 7 | |
| 8 | if (!digits || digits.length === 0) { |
| 9 | return res; |
| 10 | } |
| 11 | |
| 12 | function backtrack(i, curStr) { |
| 13 | if (curStr.length === digits.length) { |
| 14 | res.push(curStr); |
| 15 | return; |
| 16 | } |
| 17 | |
| 18 | for (const c of digitToChar[digits[i]]) { |
| 19 | backtrack(i + 1, curStr + c); |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | backtrack(0, ""); |
| 24 | return res; |
| 25 | }; |
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
| 7 | def backtrack(i, cur_str):
|
| 8 | if len(cur_str) == len(digits):
|
| 9 | res.append(cur_str)
|
| 10 | return
|
| 12 | for c in digit_to_char[digits[i]]:
|
| 13 | backtrack(i + 1, cur_str + c)
|
Objective
To systematically build all letter combinations by recursively choosing letters for each digit and backtracking after exploring each path.
Key Insight
Backtracking explores the decision tree of letter choices by advancing one digit at a time. When the current combination length matches the digits length, a complete combination is found and added to the results. The recursion explores all branches by iterating over letters mapped to the current digit and recursing with the updated combination. This approach cleanly handles variable input sizes and branching factors without nested loops.
Interview Quick-Check
Core Logic
The recursive function advances through digits, appending letters to the current combination and adding complete combinations to the result list when the base case is reached.
State & Boundaries
The base case triggers when the current combination length equals the digits length, ensuring only complete combinations are added.
Common Pitfalls & Bugs
Failing to check for empty input before starting recursion can cause errors or unnecessary computation.
Trigger Backtracking Only for Non-Empty Input and Return Results
| 15 | if digits:
|
| 16 | backtrack(0, "")
|
| 18 | return res |
Objective
To initiate the backtracking process only if the input digits string is non-empty and return the accumulated results.
Key Insight
An empty input string means no digits to map, so the result should be empty. Guarding the recursive call with a check prevents unnecessary recursion and potential errors. Returning the result list after recursion completes provides the final answer.
Interview Quick-Check
Core Logic
Checking if digits is non-empty before recursion prevents invalid access and unnecessary computation.
State & Boundaries
Returning the result list after recursion ensures all valid combinations are collected and returned.
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.
digit_to_char = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl",Define the mapping from digits to corresponding letters.
Storing the digit-to-letter mapping in a dictionary allows constant-time lookup of candidate letters for each digit during recursion.
for c in digit_to_char[digits[i]]:Iterate over all letters mapped to the current digit.
Exploring each letter choice for the current digit enables exhaustive search of all possible combinations.
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" }Complete the digit-to-letter mapping dictionary.
Including all digits from 2 to 9 ensures the mapping covers the entire valid input range, enabling correct letter retrieval for any digit.
res.append(cur_str)Add the current complete combination to the result list.
Appending a complete combination to the results preserves it before backtracking explores other branches.
if digits:Check if the input digits string is non-empty before starting recursion.
Guarding the recursive call prevents errors from accessing digits when the input is empty and avoids unnecessary computation.
def backtrack(i, cur_str):Define the recursive backtracking function with current index and combination string.
Encapsulating the recursive logic in a helper function allows clean state management and recursive exploration of all letter combinations.
returnReturn from recursion after adding a complete combination.
Terminating the current recursion branch prevents further exploration beyond the digits length, maintaining correctness.
backtrack(0, "")Start the backtracking process from index 0 with an empty combination string.
This initiates the recursive exploration of all letter combinations starting from the first digit.
return resReturn the list of all generated letter combinations.
Returning the accumulated results provides the final answer to the caller after all recursive exploration completes.
res = []Initialize an empty list to store all letter combinations.
This list accumulates all valid combinations generated by the backtracking process, serving as the final output container.
Test Your Understanding
Why is backtracking the appropriate approach for generating all letter combinations instead of iterative nested loops?
Backtracking naturally handles variable input lengths and branching factors by recursively exploring each choice and backtracking to explore alternatives, avoiding the complexity and inflexibility of nested loops for arbitrary input sizes.
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