Similar Problems

Similar Problems not available

Search Suggestions System - Leetcode Solution

LeetCode:  Search Suggestions System Leetcode Solution

Difficulty: Medium

Topics: binary-search string heap-priority-queue array sorting  

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.

Search Suggestions System Solution Code

1