Search Suggestions System
Medium · trie
A shop's search box suggests products while a customer types. You are given products, a list of different lowercase words, and search_word, the word the customer types one letter at a time.
After each letter, the box looks at everything typed so far and suggests the products that start with it. It shows at most three of them: the ones that come first in alphabetical (dictionary) order. A word comes before any longer word that starts with it, so "car" comes before "cart".
Return a list with one entry for each letter of search_word. The entry for the first k letters is the list of suggestions, in alphabetical order, after the customer has typed those k letters. It is an empty list if no product starts with them.
Examples
Example 1
Input: products = ["mouse", "monitor", "mouth", "moustache", "mop"], search_word = "mou"
Output: [["monitor", "mop", "mouse"], ["monitor", "mop", "mouse"], ["mouse", "moustache", "mouth"]]
Five products start with "mo", but only the first three alphabetically are shown. Once "mou" is typed, "monitor" and "mop" drop out.
Example 2
Input: products = ["ape", "apple", "apply", "bat"], search_word = "apx"
Output: [["ape", "apple", "apply"], ["ape", "apple", "apply"], []]
Nothing starts with "apx", so the last entry is empty.
Constraints
- 1 <= len(products) <= 1000
- 1 <= len(products[i]) <= 20
- 1 <= len(search_word) <= 1000
- products[i] and search_word contain only lowercase English letters
- All the words in products are different.