Solution: Search Suggestions System

Statement#

Given an array of strings called products and a word to search, design a system that, when each character of the searched word is typed, suggests at most three product names from products. Suggested products should share a common prefix with the searched word. If more than three products exist with a common prefix, return the three product names that appear first in lexicographical order.

Return the suggested products, which will be a list of lists after each character of searched word is typed.

Constraints:

• $1 \leq$ products.length $\leq 1000$
• $1 \leq$ products[i].length $\leq 3000$
• $1 \leq$ sum(products[i].length) $\leq 2 \times 10^3$
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• $1 \leq$ searched word.length $\leq 1000$
• The searched word consists of lowercase English letters.

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach would be to first sort the given product data in lexicographic order to help with retrieving three matching products. Next we’ll make a substring for every character of the word to be searched. We’ll search in the list of product names to check whether the current substring exists or not. If it exists, we’ll store the results (containing matching product names) for the current substring. We’ll repeat this process until we have traversed the whole list of product names.

It takes $O(n\log n)$ time to sort the given data, where $n$ is the number of product names. Given that $m$ is the number of characters in the search word, there will be $m$ substrings derived from the search word. So, it will take $O(m\times n)$ time to find the matching product names for all the substrings derived from the search word. So, the total time complexity of the search is $O(m\times n + n \log n)$. However, the space complexity of the suggested algorithm is $O(1)$.

Optimized approach using trie#

The idea is to reduce the time complexity using the trie pattern. Although it will increase the space complexity a bit, it will help us reduce the time complexity to a great extent. We can feed the products’ data into the system and create a trie out of it. Next, we can search for the required product in the recorded data.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

We’ll start by sorting out the products’ list since we want our data in lexicographic order. We’ll insert the products in the trie by creating new nodes for each new character encountered. Each node of the trie will have the following:

• A children dictionary
• A list of words to search

We’ll create a new node if the current character key doesn’t exist in the children dictionary. We’ll then append the current product to the search list of the node. If the list’s length becomes greater than three, we’ll just consider the top three elements and disregard the rest.

The highlighted lines below implement this logic:

Next, we’ll search for the given word in our trie. We’ll iterate through every character of the word and check whether the children dictionary contains the key of the current character. If there’s any data available corresponding to the current character, we’ll append it to the result array. Otherwise, we’ll append empty lists for the remaining characters of the searched word and terminate the search. In simpler terms, we’ll perform prefix matching for all possible substrings of the searched word that start with the first character of the word. For example, if we’re searching for “apple”, we’ll perform prefix matching for “a”, “ap”, “app”, “appl”, and “apple”.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To search for a word, we’ll first sort our products’ list and populate the data in the trie data structure. Then to search for a specific word, we’ll iterate through each letter of the searched word and check whether the children dictionary contains the key of the current letter or not. If there’s such a key, we’ll store the result. Else, we’ll append empty lists to the result for the remaining characters of the searched word and return.

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the total number of characters in the products array.

Explanation:

• Insert words in the trie: In the worst case, $n$ separate nodes will be created, and inserted in the trie, where $n$ is the total number of characters in the products array. So the time complexity of this operation becomes $O(n)$.

• Search for the prefix: The time complexity of searching for a prefix is $O(m)$, where $m$ is the length of the prefix.

Therefore, the overall time complexity becomes $O(n + m)$, which simplifies to $O(n)$.

Space complexity#

The space complexity of this solution is $O(n)$.

Explanation:

In the worst case, $n$ separate nodes will be created, and stored in the trie.