Search Suggestions System medium
Description
Given products and a searchWord, after each character typed return up to 3 lexicographically smallest products that have the typed prefix. Return a list of lists — one suggestion list per prefix of searchWord.
Examples
> products = ["mobile","mouse","moneypot","monitor","mousepad"]
searchWord = "mouse"
Output:
"m" -> [mobile, moneypot, monitor]
"mo" -> [mobile, moneypot, monitor]
"mou" -> [mouse, mousepad]
"mous" -> [mouse, mousepad]
"mouse" -> [mouse, mousepad]Constraints
1 <= products.length <= 1000, total chars ≤2 × 10^4, lowercase.1 <= searchWord.length <= 1000.
Intuition
This is autocomplete — the trie’s headline application. Insert all products. For each prefix of searchWord, walk to the prefix node and DFS its subtree in alphabetical order, collecting the first 3 end-of-word words. If you store products sorted and keep up to 3 at each node during insertion, each query is O(L).
Code (trie with cached top-3)
Sort once, and “top 3” becomes “first 3 inserted.” Because products are inserted in lexicographic order, the first 3 words to pass through any node are exactly its 3 smallest completions. Caching them at insert time turns each keystroke query into a pure O(1)-per-character walk — the same “precompute the answer, serve from memory” idea behind the system-design typeahead.
Analysis
- Time:
O(T log T)to sort (T = total characters) +O(T)to build +O(L)per query. - Space:
O(T)for the trie (plus up to 3 strings cached per node).
Same skin
- Typeahead / Autocomplete (Day 28) — this problem is the algorithmic core of that system-design question.
- Autocomplete warm-up — the uncached DFS version.
- Design Search Autocomplete System — adds ranking by frequency and live input on top.