Autocomplete With Prefix Matching

EasyPython

Problem

The lululemon app needs autocomplete suggestions while a member searches for products. Given a list of unique lowercase product-search words and a lowercase query, return every word that starts with the query, ordered lexicographically.

Implement autocomplete(words, query) using a trie. Each trie node should represent one character. After locating the node for the query, traverse its descendants to collect all matching words.

Formal Specification

Input: words, a list of unique lowercase strings, and query, a lowercase string.
Output: A list of matching words in lexicographic order.
Return an empty list if no word has the query as a prefix.
An empty query matches every word.

Constraints

1 <= len(words) <= 10^5
0 <= len(query) <= 50
1 <= len(word) <= 50
Words contain only lowercase English letters
All words are unique

Function Signature

def autocomplete(words, query):

Implement autocomplete(words, query) using a trie. Each trie node should represent one character. After locating the node for the query, traverse its descendants to collect all matching words.

Formal Specification

Input: words, a list of unique lowercase strings, and query, a lowercase string.
Output: A list of matching words in lexicographic order.
Return an empty list if no word has the query as a prefix.
An empty query matches every word.