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 have prefix the same as the part of sentence already typed. Here are the specific rules:
Your job is to implement the following functions:
The constructor function:
AutocompleteSystem(String[] sentences, int[] times):
This is the constructor. The input is
historical data
.
Sentences
is a string array consists of previously typed sentences.
Times
is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
List<String> input(char c):
The input
c
is the next character typed by the user. The character will only be lower-case letters (
'a'
to
'z'
), blank space (
' '
) or a special character (
'#'
). Also, the previously typed sentence should be recorded in your system. The output will be the
top 3
historical hot sentences that have prefix the same as the part of sentence already typed.
Example:
Operation:
AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you"
:
5
times
"island"
:
3
times
"ironman"
:
2
times
"i love leetcode"
:
2
times
Now, the user begins another search:
Operation:
input('i')
Output:
["i love you", "island","i love leetcode"]
Explanation:
There are four sentences that have prefix
"i"
. Among them, "ironman" and "i love leetcode" have same hot degree. Since
' '
has ASCII code 32 and
'r'
has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
Operation:
input(' ')
Output:
["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix
"i "
.
Operation:
input('a')
Output:
[]
Explanation:
There are no sentences that have prefix
"i a"
.
Operation:
input('#')
Output:
[]
Explanation:
The user finished the input, the sentence
"i a"
should be saved as a historical sentence in system. And the following input will be counted as a new search.
Note: