Design Search Autocomplete System


  • 0

    Click here to see the full article post


  • 0

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


  • 1

    @yangshun I have fixed it. Thanks.


  • 0
    S

    Excellent solution. However I want to mention that theoretically, approach 2 is no better than approach 1. Significantly better in practice though.


  • 0
    N

    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.


  • 0

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


  • 0
    S

    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?


  • 0
    B

    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?


Log in to reply
 

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