Find dictionary words that match a phone keypad digit sequence

On a standard phone keypad, each of the digits 2 to 9 is labeled with letters:

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

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

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

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

Input: words = ["hello", "hi"], number = "4355"
Output: []

hello produces 43556, which is longer than number, and hi produces 44. No word matches.