The problem
On a phone keypad, the digits 2–9 each stand for letters: 2 is abc, 3 def, 4 ghi, 5 jkl, 6 mno, 7 pqrs, 8 tuv, 9 wxyz.
Given a string of digits, return every string of letters it could spell, in any order. An empty input gives an empty list.
Examples
01
- Input
digits = "23"
- Output
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
02
- Input
digits = ""
- Output
[]
03
- Input
digits = "2"
- Output
["a", "b", "c"]
Constraints
- 0 ≤ digits.length ≤ 4
- Each digit is between 2 and 9.
The idea
Each digit is a choice of 3 or 4 letters, made independently. Choose a letter for the first digit, then for the second, and so on; when every digit has a letter, that string is an answer. Then undo the last choice and try the next letter.
“23” gives 3 × 3 = 9 strings, from ad to cf.
- Time
- O(n · 4ⁿ) — at most 4ⁿ strings of length n
- Space
- O(n) besides the answer
Solution · every language run against every case
class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] keys = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"} out, cur = [], [] def spell(i): # letters for digits[:i] are chosen if i == len(digits): out.append("".join(cur)) return for letter in keys[digits[i]]: cur.append(letter) spell(i + 1) cur.pop() spell(0) return out