Phone Keypad Predictive Text Suggestions

You are building the predictive-text feature for a classic 9-key phone keypad. Each digit from 2 to 9 maps to a group of lowercase letters:

Digits 0 and 1 map to no letters.

A word's digit encoding is obtained by replacing each of its letters with the digit whose group contains that letter. For example, the word "cat" encodes to "228" and "tree" encodes to "8733".

You are given a dictionary of distinct lowercase words and a list of queries. Each query is a non-empty string of digits ('0'–'9') representing the keys a user has pressed so far. For each query, return all dictionary words whose digit encoding starts with the query string (i.e., the query is a prefix of the word's digit encoding), sorted in ascending lexicographic order. If no word matches, return an empty list for that query.

Implement:

suggestions(words: List[str], queries: List[str]) -> List[List[str]]

where the i-th element of the result is the sorted list of suggestions for queries[i].

Examples

words = ["cat", "bat", "act", "car", "care", "dog"]
queries = ["228", "22", "2273", "364", "9"]

"228" -> ["act", "bat", "cat"] (all three encode exactly to "228")
"22" -> ["act", "bat", "car", "care", "cat"] ("22" is a prefix of "228", "227", "2273")
"2273" -> ["care"] ("care" encodes to "2273")
"364" -> ["dog"]
"9" -> []

Note that a query containing the digit 0 or 1 can never match any word, since no letter encodes to those digits.

Constraints

• 1 <= len(words) <= 10^5
• 1 <= len(words[i]) <= 20; words consist of lowercase English letters and are distinct
• 1 <= len(queries) <= 10^4
• 1 <= len(queries[i]) <= 20; queries consist of digit characters '0'–'9'
• The total number of words returned across all queries fits in memory (at most 10^6)

Aim for a solution that preprocesses the dictionary once so that each query is answered without rescanning every word.