Quick Overview

Build a structure over a word list that answers prefix queries, returning every distinct word that starts with each prefix in lexicographic order. Tests prefix-tree design, deduplication, and answering many queries without rescanning the whole list.

Return All Words Matching Each Prefix From a Word List

Company: Waymo

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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

Overview: Build a structure over a word list that answers prefix queries, returning every distinct word that starts with each prefix in lexicographic order. Tests prefix-tree design, deduplication, and answering many queries without rescanning the whole list.

You are given a list of words. Build a lookup over it that answers prefix queries: for a given prefix, report every word in the list that starts with that prefix. The lookup is built once and then queried many times, so answering a query should not rescan the whole word list. In this console version, your function receives the word list and all of the queries together and returns one answer per query. ### Function `words_with_prefix(words, prefixes)` receives `words`, a list of strings, and `prefixes`, a list of strings. It returns a list of lists of strings: the `j`-th inner list is the answer for `prefixes[j]`. ### 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 (for lowercase letters this is dictionary order, and a word comes before every longer word it is a prefix of, so `"car"` precedes `"carbon"`, which precedes `"cart"`). - If no word matches a prefix, its answer is an empty list. - Answers are returned in the same order as `prefixes`; a prefix that appears several times in `prefixes` is answered each time it appears. ### 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; `"x"` matches nothing; 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"`. ### 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`.

Constraints

  • 1 <= len(words) <= 10^4
  • 1 <= len(words[i]) <= 30
  • 1 <= len(prefixes) <= 10^4
  • 0 <= len(prefixes[j]) <= 30 (the empty prefix is allowed and matches every word)
  • words[i] and prefixes[j] contain only lowercase English letters 'a' to 'z'
  • The total number of words across all answers is at most 2 * 10^5

Examples

Input: (['lidar', 'lane', 'radar', 'lanes', 'lidar', 'map'], ['la', 'lid', 'r', 'x', ''])

Expected Output: [['lane', 'lanes'], ['lidar'], ['radar'], [], ['lane', 'lanes', 'lidar', 'map', 'radar']]

Input: (['car', 'cart', 'carbon', 'cat', 'car'], ['car', 'cart', 'ca', 'carts'])

Expected Output: [['car', 'carbon', 'cart'], ['cart'], ['car', 'carbon', 'cart', 'cat'], []]

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.

Loading coding console...

Show the approach

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