{x}
blog image

Search Suggestions System

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 <= 1000
  • 1 <= products[i].length <= 3000
  • 1 <= sum(products[i].length) <= 2 * 104
  • All the strings of products are unique.
  • products[i] consists of lowercase English letters.
  • 1 <= searchWord.length <= 1000
  • searchWord consists of lowercase English letters.

Solution Explanation: Search Suggestions System

This problem asks to design a system that suggests at most three product names from a given list (products) after each character of a searchWord is typed. The suggestions should have a common prefix with the typed portion of searchWord, and among those, the three lexicographically smallest should be returned.

The most efficient approach combines sorting and a Trie data structure.

1. Sorting:

We first sort the products array lexicographically. This allows us to easily find the lexicographically smallest suggestions later. The sorting step takes O(n log n) time, where n is the number of products.

2. Trie Data Structure:

A Trie (prefix tree) is an ideal data structure for efficiently finding strings with a common prefix. Each node in the Trie represents a character, and the path from the root to a leaf node represents a word (product).

Here's how we adapt the Trie for this problem:

  • Children: Each node has an array of children (26 children for the 26 lowercase English letters).
  • Indices: Each node stores a list (vector, arraylist, etc.) of indices from the sorted products array. These indices represent the products that have the prefix corresponding to the path from the root to this node. We store at most three indices to limit suggestions to three products.

3. Trie Construction and Search:

  • Insertion: We iterate through the sorted products. For each product, we insert it into the Trie. During insertion, we add the index of the product to the indices list of the corresponding nodes along the path in the trie representing the prefix of the product. We cap the indices list at 3.

  • Search: We iterate through the searchWord. For each character typed, we traverse the Trie based on the current prefix. We retrieve the indices list from the node reached at each step and convert those indices into the actual product suggestions using the sorted products array.

Time Complexity Analysis:

  • Sorting: O(n log n)
  • Trie Construction: O(L), where L is the total length of all products. This is because each character in each product is visited once.
  • Trie Search: O(m * k), where m is the length of searchWord and k is the maximum number of suggestions (3 in this case). The search visits each character of searchWord and retrieves at most 3 suggestions at each step.

The overall time complexity is dominated by sorting and Trie construction: O(n log n + L).

Space Complexity Analysis:

  • Sorted products array: O(n)
  • Trie: In the worst case, the Trie could store all prefixes of all products. However, since we limit the indices to at most 3 per node, the space complexity is bounded by O(L).

The overall space complexity is O(n + L).

Code Examples (Illustrative):

The provided code examples in Python, Java, C++, and Go implement this Trie-based solution effectively. They demonstrate the Trie structure, its construction, and search functionality for efficiently generating the product suggestions. Refer to those code snippets for detailed implementation.