# Design Search Autocomplete System

• The formatting for the Trie solution is off, would appreciate if you can fix it!

• @yangshun I have fixed it. Thanks.

• This post is deleted!

• Here we can also optimize the given solution by making a min-priority queue or set of size 3. So that we need not to sort the whole 100 values.
As we need only top 3 most frequent elements. So using a min-priority queue of size 3 is sufficient to do so.

• @nimxor Thanks for your suggestion. I will try to add this approach soon.

• Well, I didn't try but I don't think solution 2 can survive all possible test cases. When all input starts with 'a', doesn't it regress to kinda brute-force?

• For the Trie solution, why don't we:
Remember the node of our last time input, so we don't have to traverse from the root all over again?

• Great Trie Solution

• I think all these 3 solutions are bad.
First one very slow.
Second one weird.
Third one very slow too.

• I think three improvements can be made for the trie solution :

1. avoiding traversal from root for each input invocation by keeping track of current node and current sentence.
2. Using a string buffer instead of string.
3. Avoiding subtree traversal to get list of matching sentences . Each node can maintain a list of sentence indices. Extra space i.e. trading space for time.

• @LArch I agree, none of the solutions feels efficient due to repeated sorting and storing duplicated copies of sentences.
How about storing all sentence in a map (sentence to count). Then for a new input create a list sorted by count and repeatedly filter as more chars are seen.
Better explanation and code ... https://discuss.leetcode.com/topic/112705/fast-and-simple-explained-no-trie-no-priority-queue

• Why not save the top 3 items at each trie node.
So when you reach a node you can just return the top 3.
Traverse will be eliminated, lookup would just return t.top3 (which is a saved list).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.