Letter Combinations of a Phone Number
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
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: Digit 2 maps to "abc" and digit 3 maps to "def". All 3 × 3 = 9 combinations are listed.
Example 2:
Input: digits = ""
Output: []
Explanation: An empty input has no combinations.
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Explanation: Digit 2 maps to three letters: a, b, and c.
Examples
Example 1
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: Digit 2 maps to 'abc' and digit 3 maps to 'def', producing 9 combinations.
Example 2
Input: digits = ""
Output: []
Explanation: No digits means no possible letter combinations.
Example 3
Input: digits = "2"
Output: ["a","b","c"]
Explanation: 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)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview