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 common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
Example 1:
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].
Example 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Explanation: The only word "havana" will be always suggested while typing the search word.
Constraints:
1 <= products.length <= 10001 <= products[i].length <= 30001 <= sum(products[i].length) <= 2 * 104- All the strings of
productsare unique. products[i]consists of lowercase English letters.1 <= searchWord.length <= 1000searchWordconsists of lowercase English letters.
Solve it on LeetCode
Approaches
1. Brute Force with Sorting
Intuition:
The simplest solution to this problem is to sort the list of products first. For every typed prefix, we can iterate through all the products and check if a product starts with this prefix. If it does, we add it to our result list for that prefix until we have added 3 suggestions or exhausted the list.
Steps:
- Sort the
productsarray. - For each prefix formed by typing the search word character by character:
- Initialize an empty list to store suggestions.
- Iterate through the sorted
productslist and check if the product starts with the current prefix. - Add the product to the suggestions list and stop if we gather 3 suggestions.
- Append the list of suggestions for each prefix to the result.
Code:
- Time Complexity: O(m * n + n log n), where
nis the number of products andmis the length of the searchWord. Sorting costs O(n log n) and the nested loop costs O(m * n). - Space Complexity: O(n), for storing the sorted list and results.
2. Prefix Trie with DFS
Intuition:
We can use a Trie to represent all product names efficiently. For each character typed, we traverse the Trie to find the node representing that prefix and perform a DFS to gather the top 3 lexicographical suggestions.
Steps:
- Build a Trie with all product names.
- For each character typed:
- Traverse the Trie to find the node representing the current prefix.
- Perform a DFS from this node to collect up to 3 product suggestions.
Code:
- Time Complexity: O(m + n log n + l * m), where
mis the total number of characters in all products (for Trie insertion),n log nfor sorting, andl * mis the sum of lengths of all prefixes multiplied by max suggestions (constant time for each prefix) - Space Complexity: O(m), where
mis the total number of characters stored in the Trie.
3. Two Pointers with Binary Search
Intuition:
This approach utilizes binary search to find the starting point of the valid suggestions in the sorted products array. The addition of two pointers helps in efficiently reducing the search space as we progress through each character in the search word.
Steps:
- Sort the
productsarray. - Use binary search to efficiently find the starting index of products matching the current prefix.
- Use two pointers to narrow down the range of possible suggestions for each new character typed.
Code:
- Time Complexity: O(m + n log n), where
mis the length of the searchWord, andnis the number of products. Sorting takes O(n log n), and the search using two pointers costs O(m) for narrowing the range for each prefix. - Space Complexity: O(1) (apart from the space needed for output), since we are not using extra space for structures other than the list for output.