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

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".