On a classic phone keypad each digit key also carries letters:
| key | letters | key | letters |
|---|---|---|---|
| 2 | abc | 6 | mno |
| 3 | def | 7 | pqrs |
| 4 | ghi | 8 | tuv |
| 5 | jkl | 9 | wxyz |
Keys 0 and 1 carry no letters: they stay as the digit itself.
Write keypad_spellings(digits: str) -> list[str] that returns every string you get by replacing each digit with one of its letters (or keeping it, for 0 and 1). If digits is empty, return [].
- The strings can come back in any order; each must appear once.
keypad_spellings("27") # ["ap", "aq", "ar", "as", "bp", "bq", "br", "bs", "cp", "cq", "cr", "cs"] in some order
keypad_spellings("1") # ["1"]
keypad_spellings("508") # ["j0t", "j0u", "j0v", "k0t", "k0u", "k0v", "l0t", "l0u", "l0v"]
keypad_spellings("") # []
Constraints: 0 <= len(digits) <= 8, digits 0-9 only.
The answer can hold up to 4^8 = 65,536 strings. Aim for O(4^n · n): time proportional to the size of the answer. Don't use itertools; build the strings yourself.
Show hint
fill the string one position at a time: for the digit at position i, try each of its letters in turn, go on to position i + 1, and when all positions are filled, record the string.