Search Autocomplete Prefix
A search box wants instant prefix matches over a fixed vocabulary of phrases. As the user types each character, the box must list every vocabulary word that starts with what they've typed so far, in lexicographic order, capped at the top k matches.
Problem
Implement a class Autocomplete(words) that pre-indexes a list of words. The method suggest(prefix, k) returns up to k words from the vocabulary that start with prefix, in lexicographic ascending order.
Input
Constructor receives an array of up to 10^4 lowercase ASCII words, each up to 20 chars. suggest receives a prefix (up to 20 chars) and an integer k (1 ≤ k ≤ 50).
Output
A list of at most k words in lexicographic order.
Constraints
- Up to 10,000 words in the vocabulary
- Word and prefix length up to 20 chars
- 1 ≤ k ≤ 50
- suggest must be fast in the hot path — sorting on each call is too slow
Examples
Example 1
Input
words = ["cat", "car", "cart", "dog"]; suggest("ca", 2)Output
["car", "cart"]
Words starting with 'ca' in sorted order: car, cart, cat. Top 2 → [car, cart].
Example 2
Input
words as above; suggest("z", 5)Output
[]
No words start with 'z'.