Find dictionary words that match a phone keypad digit sequence
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
On a standard phone keypad, each of the digits 2 to 9 is labeled with 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 |
Typing a word by pressing, for each letter, the key that carries it produces a digit string; for example, `cat` produces `228`. Given a list of known words and a digit string, return every known word that produces exactly that digit string.
### Function Signature
```python
def words_for_number(words: list[str], number: str) -> list[str]:
```
`words` is the list of known words and `number` is the digit string to look up.
### Rules
- A word matches when it has the same length as `number` and, for every position `i`, the word's `i`-th letter is on the key labeled with the `i`-th digit of `number`.
- Return the matching words sorted in ascending lexicographic order. Return an empty list if no word matches.
### Constraints
- `1 <= len(words) <= 10^4`, and the words are distinct
- Each word consists of 1 to 20 lowercase English letters
- `1 <= len(number) <= 20`, and `number` contains only the digits `2` to `9`
### Examples
**Example 1**
```text
Input: words = ["dog", "fog", "cat", "act", "bat", "fod"], number = "364"
Output: ["dog", "fog"]
```
`dog` and `fog` both produce `364`. `fod` produces `363`, and `cat`, `act` and `bat` all produce `228`.
**Example 2**
```text
Input: words = ["home", "good", "gone", "hood"], number = "4663"
Output: ["gone", "good", "home", "hood"]
```
All four words produce `4663`, so all are returned, in lexicographic order.
**Example 3**
```text
Input: words = ["hello", "hi"], number = "4355"
Output: []
```
`hello` produces `43556`, which is longer than `number`, and `hi` produces `44`. No word matches.
Overview: Coding problem: given a list of known words and a digit string typed on a standard phone keypad, return every known word whose letters map to exactly that digit sequence, in sorted order. It tests string encoding, choosing a lookup structure for the dictionary, and analyzing time complexity.
Read the full LinkedIn Software Engineer interview experience this question came from
On a standard phone keypad, each of the digits 2 to 9 is labeled with 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 |
Typing a word by pressing, for each letter, the key that carries it produces a digit string; for example, `cat` produces `228`.
You are given a list of known words `words` and a digit string `number`. Return every known word that produces exactly that digit string.
### Rules
- A word matches when it has the same length as `number` and, for every position `i`, the word's `i`-th letter is on the key labeled with the `i`-th digit of `number`.
- Return the matching words sorted in ascending lexicographic order. Return an empty list if no word matches.
`number` is text of up to 20 digits; compare it as a string (read as an integer it could exceed 2^63 - 1). No other numeric values are involved.
### Constraints
- `1 <= len(words) <= 10^4`, and the words are distinct
- Each word consists of 1 to 20 lowercase English letters
- `1 <= len(number) <= 20`, and `number` contains only the digits `2` to `9`
### Examples
**Example 1**
```text
Input: words = ["dog", "fog", "cat", "act", "bat", "fod"], number = "364"
Output: ["dog", "fog"]
```
`dog` and `fog` both produce `364`. `fod` produces `363`, and `cat`, `act` and `bat` all produce `228`.
**Example 2**
```text
Input: words = ["home", "good", "gone", "hood"], number = "4663"
Output: ["gone", "good", "home", "hood"]
```
All four words produce `4663`, so all are returned, in lexicographic order.
Constraints
- 1 <= len(words) <= 10^4, and the words are distinct
- Each word consists of 1 to 20 lowercase English letters
- 1 <= len(number) <= 20, and number contains only the digits 2 to 9
Examples
Input: (['dog', 'fog', 'cat', 'act', 'bat', 'fod'], '364')
Expected Output: ['dog', 'fog']
Explanation: Source example 1: dog and fog produce 364; fod produces 363 and cat, act and bat produce 228.
Input: (['home', 'good', 'gone', 'hood'], '4663')
Expected Output: ['gone', 'good', 'home', 'hood']
Explanation: Source example 2: all four words produce 4663 and are returned in lexicographic order, not input order.
Hints
- A word whose letter count differs from the number of digits in number can never match, whatever its letters are.
- Every letter lies on exactly one key, and keys 7 and 9 carry four letters each; a match must agree with number at every position, including the last one.
- The output order is fixed by the rules (ascending lexicographic), independent of the order of words in the input.