Letter Combinations of a Phone Number
Medium · Backtracking · Hash Table · String · Backtracking
Problem
Every digit from 2 to 9 sits on a phone key that also carries letters:
- 2 — abc
- 3 — def
- 4 — ghi
- 5 — jkl
- 6 — mno
- 7 — pqrs
- 8 — tuv
- 9 — wxyz
Given a string digits, return every string of letters those keys could type, taking one letter from each key in order. Return them in any order.
Two details catch people out. Keys 7 and 9 carry four letters, not three. And an empty digits has no combinations at all: return [], not [""].
Examples
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Key 2 gives a, b or c and key 3 gives d, e or f. Every pairing is one answer: 3 × 3 = 9.
Input: digits = "" Output: []
No keys were pressed, so there is nothing to spell: an empty list, not a list holding one empty string.
Constraints
- 0 <= len(digits) <= 4
- digits[i] is a digit from '2' to '9'
Approaches
- Generate every letter string, keep the ones that fit — time O(n · 26^n), space O(n · 4^n)
Related problems
Start free on Cariara · Coding problems · System design studio
