642. Design Search Autocomplete System π
Description
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'
).
You are given a string array sentences
and an integer array times
both of length n
where sentences[i]
is a previously typed sentence and times[i]
is the corresponding number of times the sentence was typed. For each input character except '#'
, return the top 3
historical hot sentences that have the same prefix as the part of the sentence already typed.
Here are the specific rules:
- The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
- The returned top
3
hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first). - If less than
3
hot sentences exist, return as many as you can. - When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
Implement the AutocompleteSystem
class:
AutocompleteSystem(String[] sentences, int[] times)
Initializes the object with thesentences
andtimes
arrays.List<String> input(char c)
This indicates that the user typed the characterc
.- Returns an empty array
[]
ifc == '#'
and stores the inputted sentence in the system. - Returns the top
3
historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than3
matches, return them all.
- Returns an empty array
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"], ["i love you", "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"]. 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. obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ". obj.input("a"); // return []. There are no sentences that have prefix "i a". obj.input("#"); // return []. 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.
Constraints:
n == sentences.length
n == times.length
1 <= n <= 100
1 <= sentences[i].length <= 100
1 <= times[i] <= 50
c
is a lowercase English letter, a hash'#'
, or space' '
.- Each tested sentence will be a sequence of characters
c
that end with the character'#'
. - Each tested sentence will have a length in the range
[1, 200]
. - The words in each input sentence are separated by single spaces.
- At most
5000
calls will be made toinput
.
Solutions
Solution 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
|