Skip to content

Commit 8dc0e8c

Browse files
fishercoder1534fishercoder1534
committed
add 642
1 parent 55af923 commit 8dc0e8c

File tree

2 files changed

+109
-0
lines changed

2 files changed

+109
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
2222
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
2323
|644|[Maximum Average Subarray II](https://leetcode.com/problems/maximum-average-subarray-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_644.java) | |O(1) | Hard | Binary Search
2424
|643|[Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_643.java) | O(n) |O(1) | Easy |
25+
|642|[Design Search Autocomplete System](https://leetcode.com/problems/design-search-autocomplete-system/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_642.java) | O(n) |O(n) | Hard | Design
2526
|640|[Solve the Equation](https://leetcode.com/problems/solve-the-equation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_640.java) | O(n) |O(n) | Medium |
2627
|638|[Shopping Offers](https://leetcode.com/problems/shopping-offers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_638.java) | O(2^n) |O(n) | Medium | DP, DFS
2728
|637|[Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_637.java) | O(n) |O(1) | Easy |

‎src/main/java/com/fishercoder/solutions/_642.java

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.*;
4+
5+
/**
6+
* 642. Design Search Autocomplete System
7+
*
8+
* 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:
9+
10+
The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
11+
The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
12+
If less than 3 hot sentences exist, then just return as many as you can.
13+
When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
14+
Your job is to implement the following functions:
15+
16+
The constructor function:
17+
18+
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.
19+
20+
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
21+
22+
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.
23+
24+
25+
Example:
26+
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
27+
The system have already tracked down the following sentences and their corresponding times:
28+
"i love you" : 5 times
29+
"island" : 3 times
30+
"ironman" : 2 times
31+
"i love leetcode" : 2 times
32+
Now, the user begins another search:
33+
34+
Operation: input('i')
35+
Output: ["i love you", "island","i love leetcode"]
36+
Explanation:
37+
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.
38+
39+
Operation: input(' ')
40+
Output: ["i love you","i love leetcode"]
41+
Explanation:
42+
There are only two sentences that have prefix "i ".
43+
44+
Operation: input('a')
45+
Output: []
46+
Explanation:
47+
There are no sentences that have prefix "i a".
48+
49+
Operation: input('#')
50+
Output: []
51+
Explanation:
52+
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.
53+
54+
Note:
55+
The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
56+
The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
57+
Please use double-quote instead of single-quote when you write test cases even for a character input.
58+
Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see here for more details.
59+
*/
60+
public class _642 {
61+
62+
/**reference: https://discuss.leetcode.com/topic/96150/java-solution-trie-and-priorityqueue/3*/
63+
public class AutocompleteSystem {
64+
65+
Map<String, Integer> map = new HashMap<>();
66+
List<Map.Entry<String, Integer>> answers = new ArrayList<>();
67+
StringBuilder stringBuilder = new StringBuilder();
68+
69+
public AutocompleteSystem(String[] sentences, int[] times) {
70+
for (int i = 0; i < sentences.length; i++) {
71+
map.put(sentences[i], map.getOrDefault(sentences[i], 0) + times[i]);
72+
}
73+
}
74+
75+
public List<String> input(char c) {
76+
List<String> result = new ArrayList<>();
77+
if (c == '#') {
78+
map.put(stringBuilder.toString(), map.getOrDefault(stringBuilder.toString(), 0) + 1);
79+
stringBuilder.setLength(0);
80+
answers.clear();/**The use has finished typing, so we'll clean answers to get ready for next search*/
81+
} else {
82+
stringBuilder.append(c);
83+
/**when its length is 1, we find all the prefix that is a match and put them into answers,
84+
* then for the rest, we'll just remove those that are not match with the prefix any more, we do this logic in else branch*/
85+
if (stringBuilder.length() == 1) {
86+
for (Map.Entry<String, Integer> entry : map.entrySet()) {
87+
if (entry.getKey().startsWith(stringBuilder.toString())) {
88+
answers.add(entry);
89+
}
90+
}
91+
Collections.sort(answers, (a, b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());
92+
} else {
93+
for (Iterator<Map.Entry<String, Integer>> iterator = answers.iterator(); iterator.hasNext();) {
94+
if (!iterator.next().getKey().startsWith(stringBuilder.toString())) {
95+
iterator.remove();
96+
}
97+
}
98+
}
99+
100+
for (int i = 0; i < 3 && i < answers.size(); i++) {
101+
result.add(answers.get(i).getKey());
102+
}
103+
}
104+
return result;
105+
}
106+
}
107+
108+
}

0 commit comments

Comments
 (0)