DSA problem
Letter Combinations of a Phone Number
Given a string digits containing digits from 2 to 9, return all possible letter combinations that the number could represent on a classic phone keypad. The mapping is the familiar one: 2 -> "abc", 3 -> "def", 4 -> "ghi", 5 -> "jkl", 6 -> "mno", 7 -> "pqrs", 8 -> "tuv", 9 -> "wxyz". The answer may be returned in any order; if the input is empty, return an empty list.
Every digit independently chooses one of its mapped letters, so the total number of combinations is the product of the letter-set sizes — at most 4^n where n = digits.length. For digits = "23" that gives 3 * 3 = 9 strings. We need to enumerate this Cartesian product cleanly.
The classical approach is depth-first backtracking. Define backtrack(index, path) where index is the current digit position and path is the partial string built so far. When index == digits.length, the path is a full-length combination — snapshot a copy into the results and return. Otherwise, look up the letters for digits[index] and recurse for each, appending and then popping in the standard choose / recurse / un-choose dance.
An iterative BFS expansion is also a fine alternative — start with a list containing the empty string and, for each digit, replace the list with all extensions. Both run in O(4^n * n) time (the n factor is the cost of materializing each output string), and the recursive version uses O(n) extra stack space beyond the output itself.
Examples
digits = "23"["ad","ae","af","bd","be","bf","cd","ce","cf"]digits = ""[]digits = "2"["a","b","c"]Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9'].
- No digit 0 or 1 will appear in the input.
- The answer may be returned in any order.
- If digits is empty, return an empty list — not a list containing the empty string.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.