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

Prefix Lookup over a Word List

Hints

1. Remove duplicates and sort the words once. Where do all the words that begin with a given prefix end up relative to each other in that sorted list?
2. Binary search finds the first word that is not smaller than the prefix. Since every character is between 'a' and 'z', think about which string sorts just after every word that starts with the prefix.
3. A trie is the other classic build-once structure: each query walks only len(prefix) nodes, and visiting children in alphabetical order yields the answer already sorted.

Approach

Build step: remove duplicate words and sort the remaining distinct words in ascending lexicographic order. This sorted array is the data structure, built once in O(W log W) comparisons for W words. Key fact: in a sorted list of strings, all words that start with a prefix p form one contiguous block. Every such word is >= p (p is a prefix of it, and a prefix sorts no later than its extensions), and every such word is < p + '{', because '{' is the character immediately after 'z', so any word beginning with p has a letter <= 'z' (or nothing) at position len(p). Conversely, any word w with p <= w < p + '{' must begin with p: if it did not, the first position where w and p differ would place w entirely before p or entirely after p + '{'. Query step: two binary searches locate lo = the first index whose word is >= p and hi = the first index whose word is >= p + '{'; the answer is the slice sorted[lo:hi], which is already deduplicated and in ascending order. The empty prefix gives lo = 0 and hi = the end of the array, so it returns every distinct word; a prefix that matches nothing gives lo == hi and an empty list; a prefix longer than every word it resembles simply finds no word inside its range. Answers are appended in the order of prefixes, and a repeated prefix is answered each time. Each query costs O(L log W) character comparisons (L <= 30) plus the size of its answer, so no query rescans the word list. A trie gives the same results: insert each distinct word, walk the prefix, and collect the words below the reached node with children visited from 'a' to 'z'.

• Time complexity: O((W + Q) * L * log W + K * L), where W = len(words), Q = len(prefixes), L <= 30 is the maximum string length and K is the total number of words across all answers
• Space complexity: O(W * L) for the sorted distinct words, plus O(K * L) for the returned answers