642. Design Search Autocomplete System

Design a search autocomplete system that learns from user search history. Given historical sentences and their frequencies, when a character is typed, return the top 3 most frequently searched sentences with the same prefix, sorted by frequency (higher first), then lexicographically.

Examples
Input: [["AutocompleteSystem","input","input","input","input"],[[["i love you","island","iroman","i love leetcode"],[5,3,2,2]],["i"],[" "],["a"],["#"]]]
Output: [null,["i love you","island","i love leetcode"],["i love you","i love leetcode"],[],[]]
Hints
Related Problems

642. Design Search Autocomplete System

Design a search autocomplete system that learns from user search history. Given historical sentences and their frequencies, when a character is typed, return the top 3 most frequently searched sentences with the same prefix, sorted by frequency (higher first), then lexicographically.