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:

1. The suggested products should have a prefix that matches the search query.
2. The suggested products should be sorted lexicographically.
3. 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:

1. 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.

1. 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.

1. 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.

1. 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.

1. 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 List Search(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;
    }
}