Backtracking · 084Medium
Letter Combinations of a Phone Number
Given a string of digits 2-9, return all letter combinations the number could spell, using the standard telephone keypad mapping. Any order is acceptable.
Constraints
- 0 <= digits.length <= 4
- digits[i] is in the range '2'..'9'.
Examples
letterCombinations("23") -> ["ad","ae","af","bd","be","bf","cd","ce","cf"]
letterCombinations("") -> []
letterCombinations("2") -> ["a","b","c"]
letterCombinations("7") -> ["p","q","r","s"] // 7 maps to four letters
letterCombinations("79") -> 16 strings // 4 * 4, any order
letterCombinations("2345") -> 81 strings // the longest allowed inputEdge cases
- The empty string returns an empty array, NOT [""].
- 7 (pqrs) and 9 (wxyz) map to four letters, the rest to three.
- 1 and 0 never appear in the input.
Show the target complexity (spoiler)
- Naive
- There is no polynomial approach — the output itself is up to 4^n entries.
- Target
- O(4^n * n) time — backtracking over one digit per level, appending each mapped letter.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/084-letter-combinations-of-a-phone-number.js ./practice c 084