-
Notifications
You must be signed in to change notification settings - Fork 0
/
642.java
69 lines (59 loc) · 1.67 KB
/
642.java
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
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class AutocompleteSystem {
class Node {
int cnt;
String content;
private Node(int cnt, String content) {
this.cnt = cnt;
this.content = content;
}
}
StringBuilder sb = new StringBuilder();
TreeMap<Node, String> map = new TreeMap<Node, String>(new Comparator<Node>(){
@Override
public int compare(Node o1, Node o2) {
if(o1.cnt == o2.cnt) return o1.content.compareTo(o2.content);
return o2.cnt - o1.cnt;
}
});
Map<String, Node> m = new HashMap<String, Node>();
public AutocompleteSystem(String[] sentences, int[] times) {
for(int i=0; i<sentences.length; i++) {
Node t = new Node(times[i], sentences[i]);
map.put(t, sentences[i]);
m.put(sentences[i], t);
}
}
public List<String> input(char c) {
if(c == '#') {
String s = sb.toString();
if(m.containsKey(s)) {
Node t = m.get(s);
map.remove(t);
t.cnt = t.cnt + 1;
map.put(t, t.content);
} else {
Node t = new Node(1, s);
m.put(s, t);
map.put(t, s);
}
sb = new StringBuilder();
return new ArrayList<String>();
}
if(c != '#') sb.append(c);
List<String> ret = new ArrayList<String>();
String prefix = sb.toString();
for(Node k : map.keySet()) {
if(k.content.startsWith(prefix)) {
ret.add(k.content);
if(ret.size() == 3) break;
}
}
return ret;
}
}