MediumBacktracking
Letter Combinations of a Phone Number
amazongooglemetamicrosoftuberoracleapple
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.
2 → abc 3 → def 4 → ghi 5 → jkl
6 → mno 7 → pqrs 8 → tuv 9 → wxyz
Examples
Example 1
Input
digits = "23"
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]
Digit 2 maps to 'abc' and digit 3 maps to 'def', producing 9 combinations.
Example 2
Input
digits = ""
Output
[]
No digits means no possible letter combinations.
Example 3
Input
digits = "2"
Output
["a","b","c"]
A single digit 2 maps to three letters.
Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9']
Optimal complexity
Time
O(4^n)
Space
O(n)
One problem, two ways to prep
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.