设计搜索自动补全系统

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that match the prefix of the part sentence before the current character. For each input sentence, when the character is '#', it means the sentence ends, and you need to store the complete sentence into the historical data.

Implement the AutocompleteSystem class:

• AutocompleteSystem(String[] sentences, int[] times) Initializes the object with a list of historical sentences and their corresponding number of times each sentence was typed.
• List<String> input(char c)
  • If c == '#', it means the sentence ends, and you need to store the complete sentence into the historical data.
  • Otherwise, you need to return the top 3 historical hot sentences that match the prefix of the part sentence before the current character.

Example 1:

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"], [], [], []]

Explanation
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"], because "i love you" has highest times.
obj.input(" "); // return []. There's no match.
obj.input("a"); // return []. There's no match.
obj.input("#"); // return []. The sentence "i a" was typed. Store the string to the record.

Example 2:

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"], [], [], []]

Explanation
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"], because "i love you" has highest times.
obj.input(" "); // return []. There's no match.
obj.input("a"); // return []. There's no match.
obj.input("#"); // return []. The sentence "i a" was typed. Store the string to the record.

Constraints:

• 1 <= sentences.length <= 100
• 1 <= sentences[i].length <= 100
• 1 <= times.length <= 100
• times[i] >= 1
• c is a lowercase English letter, space ' ' or special character '#'
• Each input will be ended with the character '#'.