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

...

/

Search Auto-complete

Search Auto-complete

Solve a medium-level problem of designing an auto-complete feature using tries.

We'll cover the following...

Problem statement

Auto-complete is a feature—similar to one provided by search engines—that displays query suggestions in real time based on what search string a user is typing in the input field.

We're provided with a list of keywords and a query string. Design a system that provides the top three suggestions from the keyword list to the user every time the user types a character of the query string.

The suggested words should be a prefix of the query string typed so far. If there are more than three valid suggestions, return the three lexicographically smallest ones.

Example

Sample input

words: ["honey", "hammer", "hostile", "hotel", "hill", "hotdog", "hotter"]
queryWord: "hot"

Sample output

query typed so far = "h",
suggestions: ["hammer", "hill", "honey"]
query typed so far = "ho",
suggestions: ["honey", "hostile", "hotdog"]
query typed so far = "hot",
suggestions: ["hotdog", "hotel", "hotter"]

Explanation

For the query "h", words sorted in alphabetical order are ["hammer", "hill", "honey", "hostile", "hotdog", "hotel", "hotter"], out of which the top three are "hammer", "hill" and "honey".

For the query "ho", words sorted in alphabetical order are ["honey", "hostile", "hotdog", "hotel", "hotter"], out of which the top three are "honey", "hostile" and "hotdog".

For the query "hot", words sorted in alphabetical order are ["hotdog", "hotel", "hotter"], out of which the top three are "hotdog", "hotel", and "hotter".

Try it yourself

Try to solve the problem yourself before reading the solution.

C++
Java
#include <iostream>

#include <vector>

using namespace std;



vector<vector<string>> autoSuggest(vector<string> data, string queryWord){

    // your code goes here

    vector<vector<string>> answer;

    return answer;

}
Solve search autocomplete in C++

Intuition

Binary search-based approach

Since the problem asks us to return the results in sorted order, we sort the words as a first step. This sorting operation allows us to perform a binary search for a given prefix value in the words list. Once a prefix is found in the list of words, we need to add the next three words to the output suggestion list.

To summarize the steps performed in the algorithm, we sort the words list and iterate each character of the query, adding it to the prefix to search for, and then run a binary search for the prefix in the sorted word list. Then, starting from the current binary search start index, we add the next three strings to the output and continue doing this till the prefix remains the same.

Reason
autoSuggest(wordsData, queryWord) {
        // sort the words present in the datastore
        sort(wordsData)
        // create a list to store results
        result = new list(list(string))
        // define the start index and size of words list
        int newStart = 0, n = size(wordsData)
        // define a prefix string variable. It is empty at the start. 
        string prefix
        
        for every character c in queryWord {
            // append the character to the query word
            prefix += c;
            // find the starting index of the word begining with the given prefix.
            start = lower_bound(wordsData, prefix)
            // Add the words with the same prefix to the result.
            // Loop runs until `i` reaches the end of input 
            // or 3 times or till the
            // prefix is same, Whichever comes first.
            for i in range (start to min(start + 3, n))
                result.add(wordsData[i]);
            // Reduce the size of elements to perform binary search on 
            newStart = start;
        }
        return result
    }

The time complexity of the above solution is O(Nlog(N))+O(Qlog(N)) O(Nlog(N))+O(Qlog(N)) , where ...