Design Search Autocomplete System
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:
- 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 degree of hot, you need to use ASCII-code order (smaller one appears first).
- If less than 3 hot sentences exist, then just 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.
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:
- The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
- 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.
- Please use double-quote instead of single-quote when you write test cases even for a character input.
- 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.
-----------------------------------------
2个方法，
＃1 用缓存，在每个结点把所有prefix 的string的个数都存上，每次返回前3就好
＃2 不缓存。每次都重新计算
各有利弊空间vs时间，＃1会占很大空间，＃2会花很多时间，＃2过不了Leetcode的OA
#1 AutocompleteSystem - O(k * n), k 为sentence的平均长度，n为sentence的个数
input - 每一次查找是O(1), sort是O(m * lg m), m为所对应的map的size
空间那就太不一定了
＃2 AutocompleteSystem跟上面一样
input - 每一次查找是 O((26 ＋ 1)^n), n为最长string的剩余长度
Solution #1
class AutocompleteSystem {
private Node root;
private Node current;
private String sofar;
public AutocompleteSystem(String[] sentences, int[] times) {
root = new Node();
current = root;
sofar = "";
for (int i = 0; i < sentences.length; i++) {
String sentence = sentences[i];
int count = times[i];
addToMap(sentence, count);
}
}
private void addToMap(String s, int count) {
Node head = root;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if (!head.next.containsKey(c)) {
head.next.put(c, new Node());
}
Node cur = head.next.get(c);
cur.map.put(s, cur.map.getOrDefault(s, 0) + count);
head = cur;
}
}
public List<String> input(char c) {
if (c != '#') {
sofar += c;
if (current == null || !current.next.containsKey(c)) {
current = null;
return new ArrayList<String>();
}
current = current.next.get(c);
return getOrdered(current.map);
}else {
addToMap(sofar, 1);
sofar = "";
current = root;
return new ArrayList<>();
}
}
private List<String> getOrdered(Map<String, Integer> map) {
List<Map.Entry<String, Integer>> entries = new ArrayList<>(map.entrySet());
Collections.sort(entries, (a, b) -> {
if (a.getValue() == b.getValue()) return a.getKey().compareTo(b.getKey());
return b.getValue() - a.getValue();
});
List<String> rt = new ArrayList<>();
for (int i = 0; i < Math.min(3,entries.size()); i++) {
rt.add(entries.get(i).getKey());
}
return rt;
}
}
class Node {
public Map<String, Integer> map;
public Map<Character, Node> next;
public Node () {
map = new HashMap<>();
next = new HashMap<>();
}
}
/**
* Your AutocompleteSystem object will be instantiated and called as such:
* AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
* List<String> param_1 = obj.input(c);
*/
Solution #2, 不进行缓存，每次都重新把tries走一遍。这个方法过不了OA
class AutocompleteSystem {
class Node{
public Map<Character, Node> next;
public boolean isWord;
public int count;
public Node() {
count = 0;
next = new HashMap<>();
}
}
class Pair{
public String st;
public int count;
public Pair(String st, int count) {
this.st = st;
this.count = count;
}
}
private Node root;
private String sofar;
private Node cur;
public AutocompleteSystem(String[] sentences, int[] times) {
root = new Node();
sofar = "";
for (int i = 0; i < sentences.length; i++) {
addToSystem(sentences[i], times[i]);
}
}
private void addToSystem(String sentence, int time) {
Node node = root;
for (int i = 0; i < sentence.length(); i++) {
char c = sentence.charAt(i);
if (!node.next.containsKey(c)) {
node.next.put(c, new Node());
}
node = node.next.get(c);
}
node.isWord = true;
node.count += time;
}
public List<String> input(char c) {
if (c == '#') {
addToSystem(sofar, 1);
sofar = "";
return new ArrayList<>();
}else {
if (sofar.length() == 0) {
cur = root;
}
sofar += c;
if (!cur.next.containsKey(c)) {
return new ArrayList<>();
}
cur = cur.next.get(c);
List<Pair> rt = new ArrayList<>();
computeCounts(rt, cur, sofar);
Collections.sort(rt, (a, b) -> b.count - a.count);
List<String> guess = new ArrayList<>();
for (int i = 0; i < Math.min(3, rt.size()); i++) {
guess.add(rt.get(i).st);
}
return guess;
}
}
private void computeCounts(List<Pair> rt, Node node, String cur) {
if (node.isWord) {
rt.add(new Pair(cur, node.count));
}
for (Map.Entry<Character, Node> entry : node.next.entrySet()) {
String temp = cur + entry.getKey();
computeCounts(rt, entry.getValue(), temp);
}
}
}
/**
* Your AutocompleteSystem object will be instantiated and called as such:
* AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
* List<String> param_1 = obj.input(c);
*/
