MediumBacktrackingAI interview only
Letter Combinations of a Phone Number
Asked atamazongooglemetamicrosoftuberoracleapple
01 · Problem
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
02 · Examples
Example 01
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 02
Input
digits = ""
Output
[]
No digits means no possible letter combinations.
Example 03
Input
digits = "2"
Output
["a","b","c"]
A single digit 2 maps to three letters.
03 · Constraints
- 010 <= digits.length <= 4
- 02digits[i] is a digit in the range ['2', '9']
04 · Optimal complexity
- Time
- O(4^n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.