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 * 104products are unique.products[i] consists of lowercase English letters.1 <= searchWord.length <= 1000searchWord consists of lowercase English letters.Problem Overview: You are given a list of product names and a search word. As the user types each character of the search word, return up to three lexicographically smallest products that start with the current prefix.
Approach 1: Sorting and Linear Prefix Filtering (Time: O(n log n + m * n), Space: O(1) extra)
Start by sorting the product list lexicographically using sorting. For every prefix of the search word, iterate through the sorted list and collect the first three products that start with that prefix. Because the array is sorted, the first matches you encounter are already the smallest in lexicographical order. The key operation is repeated prefix comparison using string.startswith() or substring checks. This approach is easy to implement and works well when the product list is small, but scanning the full list for every prefix leads to O(m * n) checks where m is the search word length.
Approach 2: Trie Data Structure (Time: O(n * k + m * k), Space: O(n * k))
A more scalable solution uses a Trie to store product names character by character. Each node represents a prefix and stores up to three lexicographically smallest product suggestions that share that prefix. Insert every product into the Trie while maintaining a sorted list of at most three suggestions at each node. When processing the search word, traverse the Trie one character at a time and read the stored suggestions directly from the current node. This avoids scanning the entire product list repeatedly and turns the search process into simple prefix traversal.
The Trie approach leverages prefix sharing between strings, which is exactly what the problem models. It also aligns with typical autocomplete system design. Operations mainly involve character traversal and prefix lookup within the Trie, a common pattern in string and search problems.
Recommended for interviews: The Trie solution is usually what interviewers expect because it models a real-world autocomplete system and achieves predictable performance. The sorting approach still demonstrates good understanding of lexicographical ordering and prefix filtering, so it is a solid starting point during discussion before moving to the optimized Trie-based design.
This approach involves sorting the products array first and then iteratively constructing prefixes from the searchWord. For each prefix, use a simple linear search over the sorted products array to find matches. By keeping the products sorted, it ensures that we can easily pick the smallest lexicographical options.
After sorting, for every prefix of the searchWord, we traverse the sorted products list, check if the product starts with the current prefix, and collect up to three matches.
This Python code starts by sorting the list of products. As we iterate through each character of the searchWord, it builds the prefix and filters products that start with the current prefix. We then select the first three such products.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n log n) due to sorting, where n is the length of products. Each prefix search is O(n), leading to an overall complexity of O(n log n + m * n), where m is the length of searchWord.
Space Complexity: O(1) additional space is needed outside the result storage, although storing results may take O(m * 3) space.
This approach aims at using a Trie to efficiently handle prefix matching. With a Trie, we insert all product names into the Trie. As each character is typed in the searchWord, we traverse the Trie to check for the top three lexicographical matches.
Using a Trie allows us to handle the prefix matching efficiently by navigating through the structure step by step according to the current prefix.
This Python code uses a Trie structure. We create nodes for each character and keep track of the top three suggestions within the TrieNode. As searchWord is typed, we navigate the Trie and retrieve suggestions.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n m) to insert all products (where n is number of products and m is max product length), and O(k) to search for each prefix (where k is the length of searchWord).
Space Complexity: O(n m) for the Trie storage, since we store each character of every word.
| Approach | Complexity |
|---|---|
| Sorting and Linear Search Approach | Time Complexity: O(n log n) due to sorting, where n is the length of products. Each prefix search is O(n), leading to an overall complexity of O(n log n + m * n), where m is the length of searchWord. Space Complexity: O(1) additional space is needed outside the result storage, although storing results may take O(m * 3) space. |
| Trie Data Structure Approach | Time Complexity: O(n m) to insert all products (where n is number of products and m is max product length), and O(k) to search for each prefix (where k is the length of searchWord). Space Complexity: O(n m) for the Trie storage, since we store each character of every word. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Linear Prefix Filtering | O(n log n + m * n) | O(1) | Simple implementation when the product list is small or constraints are moderate |
| Trie Data Structure | O(n * k + m * k) | O(n * k) | Best for large datasets or autocomplete-style systems requiring fast prefix lookups |
Search Suggestions System - Leetcode 1268 - Python • NeetCode • 58,486 views views
Watch 9 more video solutions →Practice Search Suggestions System with our built-in code editor and test cases.
Practice on FleetCode