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 iterate each character of the searched word, adding the current character to the substring to search for. 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)$. The space complexity of this solution is $O(m)$, since we’re using a variable to store the current prefix to search for.

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.