Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i] is a digit in the range ['2', '9'].The key idea behind #17 Letter Combinations of a Phone Number is to simulate the mapping of digits to letters on a traditional phone keypad. Each digit from 2-9 corresponds to a set of characters. The task is to generate all possible letter combinations that the input digit string could represent.
A common and efficient strategy is backtracking. First, store the digit-to-letter mapping in a hash table or array. Then recursively build combinations by selecting one letter for the current digit and moving to the next digit. When the length of the current combination matches the input length, add it to the result list.
This approach systematically explores every possible combination. Because each digit can map to up to 4 letters, the number of combinations grows exponentially. The time complexity is approximately O(4^n * n), where n is the number of digits, while the recursion stack contributes O(n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with digit-to-letter mapping | O(4^n * n) | O(n) |
| BFS / Iterative combination building | O(4^n * n) | O(4^n) |
NeetCode
This approach uses recursion to explore all possible combinations represented by the digit-to-letter mapping of a phone keypad. We incrementally build letter combinations by allocating one letter per digit, and then explore further by making recursive calls.
The recursion depth is determined by the number of digits and the choices per digit. At each step, the algorithm branches into as many recursive calls as there are letters assigned to the current digit, continuing until all digits have been processed.
Time Complexity: O(3^n * 4^m), where n is the number of digits that map to 3 letters, and m is the number of digits that map to 4 letters.
Space Complexity: O(n), the maximum depth of the recursion stack is n.
1def letterCombinations(digits):
2 if not digits:
3 return []
4
5 phone_map = {'2':
This Python solution utilizes a recursive helper method backtrack to explore all combinations by trying each possible letter for each digit sequentially. The base case is when the length of the path equals the number of digits, signifying a complete combination has been constructed. The combinations list accumulates all completed combinations, which is then returned as the result.
The iterative BFS approach systematically explores all possible combinations of letter sequences by progressively building up combinations using a queue. It starts by enqueueing an empty string, and then, for each digit from the input, extends through all mapped letters, enqueuing partial solutions until all digits have been processed.
This method mimics the complete depth-first search but layers on combinations iteratively, capitalizing on the breadth search over immediate digit map expansion.
Time Complexity: O(3^n * 4^m), as methodically layers through the digit-letter expansion uniformly across a queue.
Space Complexity: O(n * 3^n * 4^m), where queue storage inflates in tandem with combination depth.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is frequently asked in technical interviews at companies like Google, Amazon, and Meta. It tests understanding of recursion, backtracking, and combinatorial generation using strings.
Yes, it can also be solved using an iterative BFS-style approach. In this method, you build combinations level by level using a queue or list, expanding each partial string with letters mapped to the next digit.
A hash table or array is typically used to store the mapping between digits and their corresponding letters on a phone keypad. This allows constant-time access when expanding combinations during recursion or iteration.
The optimal approach uses backtracking. By mapping each digit to its corresponding letters and recursively building combinations, you can systematically generate all possible strings. This approach is efficient and commonly expected in coding interviews.
The Python solution leverages a queue (deque) to perform BFS-style exploration of all letter combinations. Initially, it stores an empty string, and iteratively enqueues combinations by appending the letters mapped from current digits. The process continues until all digits have been covered, emerging with a full spectrum of possible sequences.