Search Suggestions System
Medium · Tries · Array · String · Binary Search · Trie · Sorting · Heap (Priority Queue)
Problem
A shop’s search box suggests products while the customer types. You are given the list of products and the word searchWord that the customer types, one letter at a time.
After each letter, the box shows at most three products that start with the letters typed so far. When more than three match, it shows the three that come first in alphabetical (lexicographic) order.
Return a list with one entry per letter of searchWord: the suggestions shown after that letter, in alphabetical order. An entry is an empty list when no product starts with the letters typed so far.
Examples
Input: products = ["mouse","mop","monitor","mobile","moneypot"], searchWord = "mouse" Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse"],["mouse"],["mouse"]]
In order the products are mobile, moneypot, monitor, mop, mouse. All five start with "m" and "mo", so the first three are shown. From "mou" on, only mouse matches.
Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags" Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
"b" and "ba" match four and three products. "bag" matches baggage and bags; "bags" matches only bags.
Input: products = ["havana"], searchWord = "tatiana" Output: [[],[],[],[],[],[],[]]
No product starts with "t", so every entry is empty.
Constraints
- 1 <= len(products) <= 1000
- 1 <= len(products[i]) <= 3000, and the lengths add up to at most 2 · 10^4
- the products are all different
- 1 <= len(searchWord) <= 1000
- products and searchWord use lowercase English letters only
Approaches
- Baseline: filter and sort for every prefix — time O(m · L · n log n), space O(n)
Follow-up
What if products are added and removed while customers type? The sorted array costs O(n) per insert, while the trie handles each change in O(L) if each node keeps its products in a small sorted structure instead of a fixed list of three. And if suggestions should be ranked by popularity rather than alphabetically, the same trie works with the three best-selling products at each node.
Related problems
Start free on Cariara · Coding problems · System design studio
