Search Suggestions System
The key idea
Sort the products once so any matching set is already lexicographically ordered; then for each prefix keep only the products that start with it and take the first 3. Sorting turns "3 smallest" into "first 3 still matching".
Problem
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 share a common prefix with the already typed part of searchWord. If there are more than three products with a common prefix, return the three lexicographically smallest ones.
Return a list of lists of the suggested products after each character of searchWord is typed.
Constraints
1 <= products.length <= 10001 <= products[i].length <= 30001 <= sum(products[i].length) <= 2 * 10^4- All the strings of
productsare unique. products[i]consists of lowercase English letters.1 <= searchWord.length <= 1000searchWordconsists of lowercase English letters.
Examples
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Complexity
Time: O(n*m + m^2) Space: O(n*m)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization