Return All Words Matching Each Prefix From a Word List

Given a list of words, build a data structure over it that answers prefix queries: for a given prefix, return every word in the list that starts with that prefix. The structure is built once and then queried many times, so a query should not rescan the whole word list. For this console version, your function receives the word list and all the queries together and returns one answer per query. ### Function Signature ```python def words_with_prefix(words: list[str], prefixes: list[str]) -> list[list[str]]: ``` ### Rules - A word starts with a prefix if its first `len(prefix)` characters equal the prefix. A word is a prefix of itself, and the empty prefix `""` matches every word. - If the same word appears more than once in `words`, it appears only once in an answer. - Each answer lists its words in ascending lexicographic order. If no word matches, the answer is an empty list. - Answers are returned in the same order as `prefixes`. ### Constraints - `1 <= len(words) <= 10^4` - `1 <= len(words[i]) <= 30` - `1 <= len(prefixes) <= 10^4` - `0 <= len(prefixes[j]) <= 30` - Words and prefixes contain only lowercase English letters `a` to `z`. - The total number of words across all answers is at most `2 * 10^5`. ### Examples **Example 1** - Input: `words = ["lidar", "lane", "radar", "lanes", "lidar", "map"]`, `prefixes = ["la", "lid", "r", "x", ""]` - Output: `[["lane", "lanes"], ["lidar"], ["radar"], [], ["lane", "lanes", "lidar", "map", "radar"]]` - Explanation: `"lidar"` appears twice in the input but once in each answer; the empty prefix matches all distinct words. **Example 2** - Input: `words = ["car", "cart", "carbon", "cat", "car"]`, `prefixes = ["car", "cart", "ca", "carts"]` - Output: `[["car", "carbon", "cart"], ["cart"], ["car", "carbon", "cart", "cat"], []]` - Explanation: `"car"` matches itself. No word is long enough to start with `"carts"`.