Solution: Search Suggestions System

Let's solve the Search Suggestions System problem using the Trie pattern.

We'll cover the following

Statement
Solution

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.

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:

main.java

Node.java

class SearchSuggestion {
    private Node root = new Node();
    public String printStringWithMarker(String data ,  int pValue)
    {
        String out = "";
        for(int i = 0; i < data.length(); i++)
        {
            if(i == pValue)
            {
                out += "«" + String.valueOf(data.charAt(i)) + "»";
            }
            else
                out += String.valueOf(data.charAt(i));
        }
        return out;
    }
    public void insert(String word) {
        Node node = root;
        int idx = 0;
        for (char ch : word.toCharArray()){
            System.out.println("\t\t" + printStringWithMarker(word, idx));
            idx += 1;
            int index = ch - 'a';
            // Create a new node if char does not exist in children dictionary
            if (node.child[index] == null) {
                System.out.println("\t\t" + ch + " does not exist in the children dictionary, creating a new node");
                node.child[index] = new Node();
                
            }
            node = node.child[index];
            System.out.println("\t\tCurrent node now = " + ch);
            node.searchWords.offer(word);
            System.out.println("\t\tWe'll add the searched word to the current node's search list");
            System.out.println("\t\t\tUpdated list for '" + ch +"': "+
                  node.searchWords);
            if (node.searchWords.size() > 3) {
                node.searchWords.pollLast();
            }
            
        }
        System.out.println("\n");
    }
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        // Insert each products string in Trie
        System.out.println("\n\tInserting nodes in the trie");
        for (String product : products) {
            System.out.println("\t\tInserting: '" + product + "'");
            insert(product);
        }
        return new ArrayList<>();
    }
    public static void main(String[] args){
        String[] products = {"bat", "bag", "bassinet", "bread", "cable",
               "table", "tree", "tarp"};
        String[] searchWordList = {"ba", "in", "ca", "t"};
        
        for(int i=0; i<searchWordList.length; i++){
            SearchSuggestion obj = new SearchSuggestion();
            System.out.println((i+1)+ ".\tProducts:"+ Arrays.toString(products));
            System.out.println("\tSearch keyword: "+ searchWordList[i]);
            obj.suggestedProducts(products, searchWordList[i]);
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}

Inserting Products

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

main.java

Node.java

class SearchSuggestion {
    private Node root = new Node();
    public String printStringWithMarker(String data ,  int pValue)
    {
        String out = "";
        for(int i = 0; i < data.length(); i++)
        {
            if(i == pValue)
            {
                out += "«" + String.valueOf(data.charAt(i)) + "»";
            }
            else
                out += String.valueOf(data.charAt(i));
        }
        return out;
    }
    public void insert(String word) {
        Node node = root;
        int idx = 0; 
        for (char ch : word.toCharArray()){
            System.out.println("\t\t" + printStringWithMarker(word, idx));
            idx += 1;
            int index = ch - 'a';
            // Create a new node if char does not exist in children dictionary
            if (node.child[index] == null) {
                node.child[index] = new Node();
            }
            node = node.child[index];
            node.searchWords.offer(word);
            System.out.print("\t\tUpdated list for substring '");
            for(int k = 0; k< idx ; k++)
            {
                System.out.print(word.charAt(k));
            }
            System.out.print("':");
            System.out.println(node.searchWords);
            if (node.searchWords.size() > 3) {
                node.searchWords.pollLast();
            }
        }
        System.out.println("\n");
    }
    public List<List<String>> search(String searchWord) {
        List<List<String>> result = new ArrayList<>();
        Node node = root;
        for (char ch : searchWord.toCharArray()) {
            int index = ch - 'a';
            if (node != null) {
                node = node.child[index];
            }
            //System.out.println("\t\t\t" + ch + "'s list: " + node.searchWords);
            System.out.println("\t\tWe'll append " + ch + "'s search list to our result");
            result.add(node == null ? Arrays.asList() : node.searchWords);
        }
        System.out.println("\t\tResult: " + result);
        return result;
    }
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        // Insert each products string in Trie
        System.out.println("\n\tInserting nodes in the trie");
        for (String product : products) {
            System.out.println("\t\tInserting: '" + product + "'");
            insert(product);
        }
        System.out.println("\tSearching for '" + searchWord + "'" );
        return search(searchWord);
    }
    public static void main(String[] args){
        String[] products = {"bat", "bag", "bassinet", "bread", "cable",
               "table", "tree", "tarp"};
        String[] searchWordList = {"ba", "in", "ca", "t"};
       
        for(int i=0; i<searchWordList.length; i++){
            SearchSuggestion obj = new SearchSuggestion();
            System.out.println((i+1)+ ".\tProducts:"+ Arrays.toString(products));
            System.out.println("\tSearch keyword: "+ searchWordList[i]);
            System.out.println("\tSuggested Products: " + obj.suggestedProducts(products, searchWordList[i]));
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}

Search Suggestions System

main.java

Node.java

class SearchSuggestion {
    private Node root = new Node();
    
    public void insert(String word) {
        Node node = root;
        int idx = 0; 
        for (char ch : word.toCharArray()){
            idx += 1;
            int index = ch - 'a';
            // Create a new node if char does not exist in children dictionary
            if (node.child[index] == null) {
                node.child[index] = new Node();
            }
            node = node.child[index];
            node.searchWords.offer(word);
            if (node.searchWords.size() > 3) {
                node.searchWords.pollLast();
            }
        }
    }
    public List<List<String>> search(String searchWord) {
        List<List<String>> result = new ArrayList<>();
        Node node = root;
        for (char ch : searchWord.toCharArray()) {
            int index = ch - 'a';
            if (node != null) {
                node = node.child[index];
            }
            result.add(node == null ? Arrays.asList() : node.searchWords);
        }
        return result;
    }
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        for (String product : products) {
            insert(product);
        }
        return search(searchWord);
    }
    public static void main(String[] args){
        String[] products = {"bat", "bag", "bassinet", "bread", "cable",
               "table", "tree", "tarp"};
        String[] searchWordList = {"ba", "in", "ca", "t"};
       
        for(int i=0; i<searchWordList.length; i++){
            SearchSuggestion obj = new SearchSuggestion();
            System.out.println((i+1)+ ".\tProducts:"+ Arrays.toString(products));
            System.out.println("\tSearch keyword: "+ searchWordList[i]);
            System.out.println("\tSuggested Products: " + obj.suggestedProducts(products, searchWordList[i]));
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}

Search Suggestions System

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

Sorting: Time complexity for sorting the products array becomes $O(nlogn)$ , where $n$ is the total number of products.
Insert words in the trie: In the worst case, $L$ separate nodes will be created for each product, and inserted in the trie, where $L$ is the average length of each product. Therefore, the time complexity of this operation becomes $O(n.L)$ .
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 of this solution is $O(nlogn + n. L + m)$ .

Space complexity

The space complexity of the algorithm is $O(N \times L)$ , where $N$ is the number of words in the products array and $L$ is the average length of each word.

Explanation:

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion

Solution: Search Suggestions System

Statement

Solution

Naive approach

Optimized approach using trie

Step-by-step solution construction

Just the code

Solution summary

Time complexity

Space complexity