Letter Combinations of a Phone Number
Understanding the Problem
We need to generate every possible string that a sequence of phone digits could represent. Each digit maps to a set of letters (like an old phone keypad), and we need to pick one letter per digit and combine them in order.
This is a Cartesian product. If the input is "23", digit 2 gives us {a, b, c} and digit 3 gives us {d, e, f}. The answer is every way to pick one element from each set, preserving the order of digits. That is 3 x 3 = 9 combinations.
Unlike problems where we choose from a single pool, here each position in the result draws from a different pool of letters. The length of every output string is exactly the number of digits in the input, so there is no variable-length decision to make. We need to systematically explore all choices.
Key Constraints:
0 <= digits.length <= 4: With at most 4 digits and at most 4 letters per digit (7 and 9), the output has at most 4^4 = 256 combinations. The input size never forces an optimization, so the choice between approaches comes down to clarity rather than performance.digits[i]is in range['2', '9'], No need to handle digits 0 or 1, which do not map to letters.
Approach 1: Iterative BFS-Style
Intuition
Build the combinations layer by layer. Start with an empty string. For the first digit, generate all single-character strings from its letters. For the second digit, take each existing string and append each letter of the second digit. Keep going until all digits are processed.
This is a breadth-first expansion. At each step, the number of partial combinations multiplies by the number of letters the current digit maps to. It needs only a list and no recursion.
Algorithm
- Create a mapping from each digit to its letters.
- Initialize a list of results with a single empty string
[""]. - For each digit in the input, create a new empty list. For each existing combination, append each letter of the current digit to get new combinations. Replace the current list with the new list.
- Return the final list. If the input is empty, return an empty list immediately.
Example Walkthrough
Code
- Time Complexity: O(n * 4^n). Where n is the length of digits. Each digit maps to at most 4 letters, so there are up to 4^n total combinations. Building each combination involves O(n) string concatenation.
- Space Complexity: O(4^n). We store all combinations in the result list at every step. At the final step, there are up to 4^n combinations.
The iterative approach allocates a full new list at every layer and rebuilds each partial string from scratch. The next approach uses recursion to build a single combination in place, one digit at a time, which lowers the auxiliary space.
Approach 2: Backtracking (Optimal)
Intuition
Instead of building combinations layer by layer, recurse one digit at a time. For the current digit, pick one of its letters, add it to the combination being built, and recurse on the remaining digits. Once all digits are processed, the combination is complete and we record it, then undo the last choice and try the next letter.
This is backtracking. Each recursive call holds a digit index and the prefix built so far, then tries each letter for that digit. Every digit position has a fixed set of choices, so each distinct sequence of choices is a distinct root-to-leaf path, and every leaf is a valid combination. No path is pruned, because there is no invalid combination to reject.
Algorithm
- Create a mapping from each digit to its letters.
- Start a recursive function with index 0 and an empty string as the current combination.
- Base case: if the index equals the length of digits, add the current combination to results.
- Recursive case: get the letters for
digits[index]. For each letter, append it to the current combination and recurse withindex + 1. - Return the collected results.
Example Walkthrough
Code
- Time Complexity: O(n * 4^n). Where n is the length of digits. The recursion tree has at most 4^n leaves. At each leaf, we create a string of length n, costing O(n).
- Space Complexity: O(n). The recursion stack goes n levels deep. The current combination being built takes O(n) space. The output is not counted as auxiliary space.