Solution: Search Suggestions System
Explore how to implement a search suggestions system by building and using a trie data structure. Learn to sort product names, store prefixes, and return up to three lexicographically sorted suggestions as each character of the searched word is typed. Understand the time and space complexity tradeoffs involved in this optimized approach.
Statement
Given an array of strings called products and a word to search, design a system that, when each character of the searched word is typed, suggests at most three product names from products. Suggested products should share a common prefix with the searched word. If more than three products exist with a common prefix, return the three product names that appear first in lexicographical order.
Return the suggested products, which will be an array of arrays after each character of searched word is typed.
Constraints:
-
products.length -
products[i].length