Generate Every Letter String a Phone Keypad Digit Sequence Can Spell
Company: Headway
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
On a standard telephone keypad, each of the digits 2 through 9 carries a set of letters:
| Digit | Letters |
| --- | --- |
| 2 | a b c |
| 3 | d e f |
| 4 | g h i |
| 5 | j k l |
| 6 | m n o |
| 7 | p q r s |
| 8 | t u v |
| 9 | w x y z |
Given a string of digits, return every letter string that the digits can spell, choosing one letter from the key of each digit.
The interview asked a variation of this keypad task; the variation itself was not described, so this console poses the base task.
### Function Signature
```python
def keypad_letter_strings(digits: str) -> list[str]:
```
### Rules
- Every output string has the same length as `digits`, and its `i`-th letter is one of the letters on the key of `digits[i]`.
- Return every such string exactly once.
- Return the strings in ascending lexicographic order.
### Constraints
- `1 <= len(digits) <= 8`
- Every character of `digits` is one of `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`
- The output therefore has at most `4^8 = 65,536` strings, each of length at most 8
### Examples
**Example 1**
```text
Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
```
Key 2 offers `a`, `b`, `c` and key 3 offers `d`, `e`, `f`, giving 3 × 3 = 9 strings.
**Example 2**
```text
Input: digits = "7"
Output: ["p", "q", "r", "s"]
```
**Example 3**
```text
Input: digits = "92"
Output: ["wa", "wb", "wc", "xa", "xb", "xc", "ya", "yb", "yc", "za", "zb", "zc"]
```
Key 9 has four letters, so there are 4 × 3 = 12 strings, listed in lexicographic order.
Overview: Given a string of digits from 2 to 9, return every letter string those digits can spell on a standard phone keypad, in lexicographic order. It tests systematic enumeration of combinations, keys that carry four letters, and producing a deterministic output order.
On a standard telephone keypad, each of the digits 2 through 9 carries a set of letters:
| Digit | Letters |
| --- | --- |
| 2 | a b c |
| 3 | d e f |
| 4 | g h i |
| 5 | j k l |
| 6 | m n o |
| 7 | p q r s |
| 8 | t u v |
| 9 | w x y z |
Given a string of digits, return every letter string that the digits can spell, choosing one letter from the key of each digit. (The interview asked an undescribed variation of this keypad task; this console poses the base task.)
Implement `keypad_letter_strings(digits)`:
- Every output string has the same length as `digits`, and its `i`-th letter is one of the letters on the key of `digits[i]`.
- Return every such string exactly once.
- Return the strings as a list in ascending lexicographic order.
### Constraints
- `1 <= len(digits) <= 8`
- Every character of `digits` is one of `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`
- The output therefore has at most `4^8 = 65,536` strings, each of length at most 8
- No integer crosses the function boundary, so no value can exceed 2^31 - 1
### Example 1
```text
Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
```
Key 2 offers `a`, `b`, `c` and key 3 offers `d`, `e`, `f`, giving 3 x 3 = 9 strings.
### Example 2
```text
Input: digits = "92"
Output: ["wa", "wb", "wc", "xa", "xb", "xc", "ya", "yb", "yc", "za", "zb", "zc"]
```
Key 9 has four letters, so there are 4 x 3 = 12 strings, listed in lexicographic order.
Constraints
- 1 <= len(digits) <= 8
- Every character of digits is one of '2', '3', '4', '5', '6', '7', '8', '9'
- The output therefore has at most 4^8 = 65,536 strings, each of length at most 8
- No integer crosses the function boundary, so no value can exceed 2^31 - 1
Examples
Input: ('23',)
Expected Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
Explanation: Source example 1: keys 2 (abc) and 3 (def) give 3 x 3 = 9 strings; output list length 9.
Input: ('92',)
Expected Output: ['wa', 'wb', 'wc', 'xa', 'xb', 'xc', 'ya', 'yb', 'yc', 'za', 'zb', 'zc']
Explanation: Source example 3: digits in descending key order; 4 x 3 = 12 strings sorted lexicographically, not by key order; output list length 12.
Hints
- The number of strings is the product of the key sizes of the digits, e.g. 3 x 3 = 9 for "23" and 4 x 3 = 12 for "92".
- Keys 7 and 9 carry four letters while every other key carries three, so do not assume a fixed key size.
- All output strings have the same length, so their lexicographic order is decided by the first position where they differ; think about how that relates to the order in which you produce them.