Solution For Search Suggestions System
Problem description:
The Search Suggestions System problem on LeetCode is designed to solve the search query problem in a given list of products. In this problem, you are given a list of products and a search query. The goal is to return a list of lists of suggested products based on the search query. The returned list of suggested products must have the following properties:
- The suggested products should have a prefix that matches the search query.
- The suggested products should be sorted lexicographically.
- The maximum number of suggested products should be 3.
Example:
Consider a list of products [“mobile”, “mouse”, “moneypot”, “monitor”, “mousepad”] and a search query “mouse”. Then, the output should be [[“mobile”, “moneypot”, “monitor”], [“mouse”, “mousepad”], [“mousepad”], [“monitor”], [“mobile”, “moneypot”, “monitor”]].
Here, the first three products in the output list correspond to the prefix “mou” in the search query. Similarly, the next three correspond to the prefix “mous”, and the last two correspond to the prefix “mouse”.
Solution:
One of the most optimal solutions to this problem is to create a trie data structure that stores all the products in the list. After that, we can traverse the trie to find all the products that match the search query. Finally, we sort the matched products lexicographically and return only the top 3 suggestions.
The following is the detailed solution for this problem:
- Create a trie data structure:
Create a trie data structure that stores all the products in the list. Each node of the trie will have a boolean flag to indicate if a product ends at that node. A product will end at a node if it is a leaf node and has a value.
- Insert all products in the trie:
We will traverse the trie to insert all the products in the trie. For each product, we will create a new branch in the trie starting from the root node. We will add a node for each character in the product, and set the boolean flag to true at the last node of the product.
- Traverse the trie to find matching products:
Traverse the trie to find all the products that match the search query. We will start at the root node and traverse each level of the trie using the characters in the search query. We will stop traversing the trie if there are no more characters in the search query or there are no more nodes in the trie that correspond to the search query.
- Sort the matched products lexicographically:
Sort the matched products lexicographically by traversing the trie to get all the products that match the search query. We will add all matching products in a list and sort them using the sorted function in Python.
- Return top 3 suggestions:
Return only the top 3 suggestions from the sorted matched products list.
Time Complexity:
The time complexity of this solution is O(NMlogM), where N is the number of products and M is the maximum length of a product. The space complexity is also O(NM).
Conclusion:
The Search Suggestions System problem is a classic trie data structure problem. In this article, we have explored a detailed solution to this problem. We have also discussed the time and space complexity of this solution.
Step by Step Implementation For Search Suggestions System
class Solution { public List> suggestedProducts(String[] products, String searchWord) { // sort the products alphabetically Arrays.sort(products); // create a map of all prefixes to the list of products with that prefix Map
> prefixMap = new HashMap<>(); for (String product : products) { for (int i = 1; i <= product.length(); i++) { String prefix = product.substring(0, i); prefixMap.putIfAbsent(prefix, new ArrayList<>()); prefixMap.get(prefix).add(product); } } // create a list of lists of products, where each list corresponds to the products // with the prefix of the current letter in the search word List > suggestedProducts = new ArrayList<>(); for (int i = 1; i <= searchWord.length(); i++) { String prefix = searchWord.substring(0, i); List
productsWithPrefix = prefixMap.getOrDefault(prefix, new ArrayList<>()); suggestedProducts.add(productsWithPrefix.subList(0, Math.min(3, productsWithPrefix.size()))); } return suggestedProducts; } }
class Solution: def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]: # create a Trie data structure to store all the products Trie = lambda: collections.defaultdict(Trie) trie = Trie() for i, product in enumerate(products): # insert each product into the Trie node = trie for c in product: node = node[c] # store the index of the product in the Trie node node['#'] = i # create a list to store the suggested products res = [] node = trie # for each character in the search word for c in searchWord: # if the character is not in the Trie if c not in node: # add an empty list to the result res.append([]) else: # otherwise, search the Trie for products starting with that character node = node[c] # create a list to store the products starting with that character products = [] # perform a depth first search on the Trie stack = [node] while stack: node = stack.pop() # if the node has a product index stored if '#' in node: # add the product to the list products.append(products[node['#']]) # add all the child nodes to the stack stack.extend(node.values()) # sort the list of products alphabetically products.sort() # add the first 3 products to the result res.append(products[:3]) # return the result return res
var searchSuggestions = function(products, searchWord) { // Initialize a trie let trie = new Trie(); // Insert all products into the trie for (let product of products) { trie.insert(product); } // Perform a depth-first search on the trie to find all words that start with the search word let words = trie.dfs(searchWord); // Sort the words in alphabetical order words.sort((a, b) => a.localeCompare(b)); // Return the first 3 words return words.slice(0, 3); }; // Trie Node class TrieNode { constructor() { this.children = {}; this.isEnd = false; } } // Trie class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let node = this.root; for (let i = 0; i < word.length; i++) { let c = word.charAt(i); if (!node.children[c]) { node.children[c] = new TrieNode(); } node = node.children[c]; } node.isEnd = true; } dfs(word) { let node = this.root; let words = []; for (let i = 0; i < word.length; i++) { let c = word.charAt(i); if (!node.children[c]) { return words; } node = node.children[c]; } this.findWords(node, word, words); return words; } findWords(node, word, words) { if (node.isEnd) { words.push(word); } for (let c in node.children) { this.findWords(node.children[c], word + c, words); } } }
vector> suggestedProducts(vector & products, string searchWord) { unordered_map > m; for (auto a: products) { string key = ""; for (char c: a) { key += c; m[key].push_back(a); } } // for (auto it = m.begin(); it != m.end(); it++) { // cout << it->first << ": "; // for (string s: it->second) cout << s << " "; // cout << endl; // } vector > res; string key = ""; for (char c: searchWord) { key += c; if (m.find(key) == m.end()) res.push_back({}); else { vector v = m[key]; sort(v.begin(), v.end()); if (v.size() > 3) v.resize(3); res.push_back(v); } } return res; }
using System; using System.Collections.Generic; public class TrieNode { public TrieNode[] children = new TrieNode[26]; public bool isWord; } public class Trie { public TrieNode root = new TrieNode(); public void Insert(string word) { TrieNode node = root; foreach (char c in word) { if (node.children[c - 'a'] == null) { node.children[c - 'a'] = new TrieNode(); } node = node.children[c - 'a']; } node.isWord = true; } public ListSearch(string prefix) { List result = new List (); TrieNode node = root; foreach (char c in prefix) { if (node.children[c - 'a'] == null) { return result; } node = node.children[c - 'a']; } DFS(node, prefix, result); return result; } public void DFS(TrieNode node, string prefix, List result) { if (node.isWord) { result.Add(prefix); } for (int i = 0; i < 26; i++) { if (node.children[i] != null) { DFS(node.children[i], prefix + (char)('a' + i), result); } } } } public class Solution { public IList > SuggestedProducts(string[] products, string searchWord) { Array.Sort(products); Trie trie = new Trie(); foreach (string product in products) { trie.Insert(product); } List > result = new List >(); string prefix = ""; foreach (char c in searchWord) { prefix += c; result.Add(trie.Search(prefix)); } return result; } }