Click here to see the full article post
@yangshun I have fixed it. Thanks.
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?
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 :
- avoiding traversal from root for each input invocation by keeping track of current node and current sentence.
- Using a string buffer instead of string.
- 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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.