Advanced Data Structures: Implementing Tries in C++ and Java/

...

Solution Review: Search Auto-Complete Optimized

See the solution to the problem challenge.

We'll cover the following...

C++

Java

#include <iostream>
#include <vector>
#include <set>
using namespace std;

// Definition of a trie node
class TrieNode
{
    public:
       	// children array to store pointer to TrieNode of next 26 alphabets
        TrieNode *children[26];
        // a set to store all the words passing through this trie node
        set<string> wordsPassingFromHere;
};

class Trie
{
    TrieNode * root;

    public:
        Trie()
        {
            root = new TrieNode();
        }

        // Inserts the string in trie
        void insert(string s)
        {
            // Points curr to the root of trie.
            TrieNode *curr = root;

            // iterate through the chacraters of the word
            for (char &c: s)
            {
                // if a child node is not found, create one
                if (curr->children[c - 'a'] == nullptr)
                    curr->children[c - 'a'] = new TrieNode();

                // move to the child node
                curr = curr->children[c - 'a'];

                // insert the word in current node's wordsPassingFromHere list
                curr->wordsPassingFromHere.insert(s);

                // if after insertion, the set size exceeds 3
                // erase the last element of the set
                if (curr->wordsPassingFromHere.size() > 3)
                {
                    // Get the iterator
                    set<string>::iterator it;

                    // Get the position of last element to be deleted
                    it = prev(curr->wordsPassingFromHere.end());
                    
                    // erase the last element from set
                    curr->wordsPassingFromHere.erase(it);
                }
            }
        }

        vector<string> returnSuggestions(set<string> suggestions){
            // store them in a vector and return 
            vector<string> v(suggestions.begin(), suggestions.end());
            return v;
        }
        
        vector<string> getWordsStartingWith(string & prefix)
        {
            // point the current node to the root
            TrieNode *curr = root;

            // Move curr to the end of prefix in its trie representation
            for (char &c: prefix)
            {
                // if the complete query word is not found 
                // in the store, terminate the search and return results
                if (curr->children[c - 'a']==nullptr)
                    return returnSuggestions(curr->wordsPassingFromHere);
                
                // move to the child node
                curr = curr->children[c - 'a'];
            }

            //retrieve the words to be returned
            return returnSuggestions(curr->wordsPassingFromHere);
        }
};

vector<vector < string>> autoSuggest(vector<string> &words, string searchWord)
{
   	// initialize a trie
    Trie *trie = new Trie();

   	// initialize a result vector
    vector<vector < string>> result;

   	// insert all words into trie
    for (string w: words)
        trie->insert(w);

    string prefix;

   	// iterate through word's characters
    for (char c: searchWord)
    {
       	// keep appending letters to the prefix
        prefix += c;
       	// fetch words starting with the current prefix
        result.push_back(trie->getWordsStartingWith(prefix));
    }

    return result;
}

Solve search auto-complete optimized in C++

Intuition

This problem is an extension of the search auto-complete. Similar to the search auto-complete problem, approaches like binary search can solve this. But in this problem, we have a restriction to optimize the search time for a query.

In the original solution, upon receiving a query prefix we would traverse the trie until the last node of the prefix, and following that, we would perform DFS to collect all the words under the trie node. However, the preorder trie traversal using DFS to gather the words increased the response time. So now we intend to reduce search time.

To do so, we must eliminate the traversal (DFS) step. One way is to store the list of words in the trie node itself. We introduce a new parameter in the trie node definition called wordsPassingFromHere. It is a sorted set with a maximum size of $3$ since the problem asks us to serve the top three suggestions in lexicographical order. For example, if we have a word home, all the four trie nodes (h, o, m, e) in the word path must contain the word home in their wordsPassingFromHere list.

So, in this case, while searching for a query prefix, we traverse to the last node of the prefix and return the wordsPassingFromHere associated with the trie node. Since returning a set is a constant time operation, this optimizes our search time.

Algorithm

The summary of the algorithm is given below.

Step 1: Build a trie of words

We create a trie from the given word list input. While inserting a word in the trie, we add the word in the wordsPassingFromHere list of all the nodes encountered in the path.

Step 2: Retrieve the suggestions

For serving the suggestions, we iterate each character of the query word, adding it to the prefix to search. After adding the current character to the prefix, we move the trie pointer to the node representing the last character of the prefix string. We return the wordsPassingFromHere list associated with the last node of the query prefix as auto-complete suggestions.

Visualization

Let's try to understand this better with the help of the example given above.

1.Introduction to Tries

2.Prefix Search

3.Suffix Search

4.Bitwise Tries

5.Pattern Matching

6.File Systems

7.Trie Traversal

8.Search Engine

9.Miscellaneous

10.Conclusion

Solution Review: Search Auto-Complete Optimized

Solution

Intuition

Algorithm

Visualization

Complexity analysis

Variables