Search Suggestions System

Problem Description

You are given an array of strings products and a string searchWord. Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have a common prefix with searchWord. If there are more than three products with a common prefix, return the three lexicographically minimum products. Return a list of lists of the suggested products after each character of searchWord is typed.

Key Insights

• The products need to be sorted lexicographically to facilitate the retrieval of the smallest products.
• A prefix search can be efficiently implemented using a Trie data structure.
• After typing each character, we will filter the products based on the current prefix and return the top three suggestions.

Space and Time Complexity

Time Complexity: O(N log N + M * L), where N is the number of products, M is the length of the searchWord, and L is the average length of the product names. The sorting of products takes O(N log N) while the prefix search for M characters takes O(M * L).

Space Complexity: O(N), for storing the sorted list of products.

Solution

To solve this problem, we will:

1. Sort the products array to ensure the suggestions are in lexicographical order.
2. Iterate through each character of searchWord and build the current prefix.
3. For each prefix, filter the sorted products to find all that start with the current prefix.
4. Select the first three products from this filtered list as suggestions.
5. Store the suggestions for each prefix and return the complete list.

Code Solutions