DSA problem
Search Suggestions System
You are given an array of strings products and a string searchWord. Design a system that, after each character of searchWord is typed, returns at most three suggested products from products that share the prefix typed so far. If there are more than three products matching the prefix, return the three lexicographically smallest. Return the suggestions for every prefix as a list of lists.
This is the classic autocomplete problem: imagine a search bar where, as the user types one character at a time, the UI must display a short list of relevant completions. The answer is a list whose i-th entry corresponds to the prefix searchWord[0..i], and each entry contains at most three products.
A clean trie-based approach inserts every product into a trie and stores at every node the three lexicographically smallest products whose prefix reaches that node. After insertion, answering each prefix becomes an O(L) walk: follow the prefix characters and return the precomputed list at the terminal node (or an empty list if the walk fails).
An equally valid and often simpler approach sorts products lexicographically once, then for each prefix uses binary search (lower_bound) to find the first product greater than or equal to the prefix and slices up to three products from that position, keeping only those that still start with the prefix. Either solution gives O((N log N + |searchWord| * log N) ) overall time without the constant factor of a Trie, while the Trie variant gives a cleaner amortized O(L) per prefix lookup at the cost of extra space.
Examples
products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]products = ["havana"], searchWord = "havana"[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"[["baggage","banner","box"],["baggage","banner"],["baggage"],["bags"]]Constraints
- 1 <= products.length <= 1000
- 1 <= products[i].length <= 3000
- 1 <= sum(products[i].length) <= 2 * 10^4
- All strings in products are unique and consist of lowercase English letters.
- 1 <= searchWord.length <= 1000 and searchWord consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.