Solution

Approach #1 Brute Force [Time Limit Exceeded]

In this solution, we make use of a HashMap $$map$$ which stores entries in the form $$(sentence_i, times_i)$$ . Here, $$times_i$$ refers to the number of times the $$sentence_i$$ has been typed earlier.

AutocompleteSystem: We pick up each sentence from $$sentences$$ and their corresponding times from the $$times$$ , and make their entries in the $$map$$ appropriately.

input(c): We make use of a current sentence tracker variable, $$cur_sen$$ , which is used to store the sentence entered till now as the input. For $$c$$ as the current input, firstly, we append this $$c$$ to $$cur_sen$$ and then iterate over all the keys of $$map$$ to check if a key exists whose initial characters match with $$cur_sen$$ . We add all such keys to a $$list$$ . Then, we sort this $$list$$ as per our requirements, and obtain the first three values from this $$list$$ .

Performance Analysis

• AutocompleteSystem() takes $$O(k*l)$$ time. This is because, putting an entry in a hashMap takes $$O(1)$$ time. But, to create a hash value for a sentence of average length $$k$$ , it will be scanned atleast once. We need to put $$l$$ such entries in the $$map$$ .

• input() takes $$O\big(n+mlog(m)\big)$$ time. We need to iterate over the list of sentences, in $$map$$ , entered till now(say with a count $$n$$ ), taking $$O(n)$$ time, to populate the $$list$$ used for finding the hot sentences. Then, we need to sort the $$list$$ of length $$m$$ , taking $$O\big(mlog(m)\big)$$ time.

Approach #2 Using One level Indexing[Accepted]

This method is almost the same as that of the last approach except that instead of making use of simply a HashMap to store the sentences along with their number of occurences, we make use of a Two level HashMap.

Thus, we make use of an array $$arr$$ of HashMapsEach element of this array, $$arr$$ , is used to refer to one of the alphabets possible. Each element is a HashMap itself, which stores the sentences and their number of occurences similar to the last approach. e.g. $$arr[0]$$ is used to refer to a HashMap which stores the sentences starting with an 'a'.

The process of adding the data in AutocompleteSystem and retrieving the data remains the same as in the last approach, except the one level indexing using $$arr$$ which needs to be done prior to accessing the required HashMap.

Performance Analysis

• AutocompleteSystem() takes $$O(k*l+26)$$ time. Putting an entry in a hashMap takes $$O(1)$$ time. But, to create a hash value for a sentence of average length $$k$$ , it will be scanned atleast once. We need to put $$l$$ such entries in the $$map$$ .

• input() takes $$O\big(s+mlog(m)\big)$$ time. We need to iterate only over one hashmap corresponding to the sentences starting with the first character of the current sentence, to populate the $$list$$ for finding the hot sentences. Here, $$s$$ refers to the size of this corresponding hashmap. Then, we need to sort the $$list$$ of length $$m$$ , taking $$O\big(mlog(m)\big)$$ time.

Approach #3 Using Trie[Accepted]

A Trie is a special data structure used to store strings that can be visualized like a tree. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent node to its children. These 26 pointers are nothing but pointers for each of the 26 letters of the English alphabet A separate edge is maintained for every edge.

Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefixes of length 1 are stored at until level 1, all prefixes of length 2 are sorted at until level 2 and so on.

A Trie data structure is very commonly used for representing the words stored in a dictionary. Each level represents one character of the word being formed. A word available in the dictionary can be read off from the Trie by starting from the root and going till the leaf.

By doing a small modification to this structure, we can also include an entry, $$times$$ , for the number of times the current word has been previously typed. This entry can be stored in the leaf node corresponding to the particular word.

Now, for implementing the AutoComplete function, we need to consider each character of the every word given in $$sentences$$ array, and add an entry corresponding to each such character at one level of the trie. At the leaf node of every word, we can update the $$times$$ section of the node with the corresponding number of times this word has been typed.

The following figure shows a trie structure for the words "A","to", "tea", "ted", "ten", "i", "in", and "inn", occuring 15, 7, 3, 4, 12, 11, 5 and 9 times respectively.

Similarly, to implement the input(c) function, for every input character $$c$$ , we need to add this character to the word being formed currently, i.e. to $$cur_sent$$ . Then, we need to traverse in the current trie till all the characters in the current word, $$cur_sent$$ , have been exhausted.

From this point onwards, we traverse all the branches possible in the Trie, put the sentences/words formed by these branches to a $$list$$ along with their corresponding number of occurences, and find the best 3 out of them similar to the last approach. The following animation shows a typical illustration.

!?!../Documents/642_Design_Autocomplete.json:1000,563!?!

Performance Analysis

• AutocompleteSystem() takes $$O(k*l)$$ time. We need to iterate over $$l$$ sentences each of average length $$k$$ , to create the trie for the given set of $$sentences$$ .

• input() takes $$O\big(p+q+mlog(m)\big)$$ time. Here, $$p$$ refers to the length of the sentence formed till now, $$cur_sen$$ . $$q$$ refers to the number of nodes in the trie considering the sentence formed till now as the root node. Again, we need to sort the $$list$$ of length $$m$$ indicating the options available for the hot sentences, which takes $$O\big(mlog(m)\big)$$ time.

Analysis written by: @vinod23