612. Search Suggestions System
You are building the autocomplete for a shop. You get an array products of distinct lowercase product names and a lowercase string searchWord that a customer types one character at a time.
After each typed character — that is, for every prefix of searchWord — suggest up to three product names that start with what has been typed so far. When more than three qualify, suggest the three lexicographically smallest, and always list suggestions in lexicographic order. Return the suggestions as a list of lists, one inner list per typed character (an inner list is empty when nothing matches).
Example 1:
Input: products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]
Explanation: After 'm' and 'mo', four products match — the three alphabetically smallest are mobile, moneypot, monitor. From 'mou' onward only mouse and mousepad remain.
Example 2:
Input: products = ["havana"], searchWord = "tatiana"
Output: [[], [], [], [], [], [], []]
Explanation: No prefix of "tatiana" matches "havana", so every one of the 7 keystrokes gets an empty suggestion list.
Constraints:
- 1 ≤ products.length ≤ 1000
- 1 ≤ products[i].length ≤ 30
- 1 ≤ searchWord.length ≤ 30
- All product names are distinct and consist of lowercase English letters; searchWord consists of lowercase English letters.
Hints:
Sort the products once. In a sorted list, all words sharing a prefix sit in one contiguous block — so the three smallest matches are simply the first three entries of that block.
You can find the block's start with a binary search for the prefix (first word >= prefix), then verify at most three entries. Or go further: build a trie and store, at every node, the up-to-3 smallest words passing through it — inserting words in sorted order keeps each cache correct for free.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"], searchWord = "mouse"
Expected output: [["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]