Given a list of distinct products and a string search_word, imagine the user types search_word
one character at a time. After each character, suggest at most 3 products that start with the text typed
so far, choosing the lexicographically smallest ones (in increasing order). Return a list with one
suggestion list per typed character.
Examples
Input: products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"], search_word = "mouse"
Output: [["mobile", "moneypot", "monitor"], ["mobile", "moneypot", "monitor"], ["mouse", "mousepad"], ["mouse", "mousepad"], ["mouse", "mousepad"]]
Input: products = ["bags", "baggage", "banner", "box", "cloths"], search_word = "bags"
Output: [["baggage", "bags", "banner"], ["baggage", "bags", "banner"], ["baggage", "bags"], ["bags"]]
Constraints
0 <= len(products) <= 5000, lowercase words of length<= 201 <= len(search_word) <= 20- Once no product matches a prefix, every later suggestion list is empty
- Target: build in
O(total characters); each suggestion should stop exploring after three matches are found
Goals
- Follow a trie one typed character at a time
- Collect the lexicographically smallest completions with an ordered DFS