This page explains Java solution to problem Design Search Autocomplete System using Trie data structure.
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:
1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
2. 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).
3. If less than 3 hot sentences exist, then just return as many as you can.
4. 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:
DesignSearchAutocompleteSystem(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.
Operation:
DesignSearchAutocompleteSystem(
["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.
package com.vc.hard;
import java.util.*;
class DesignSearchAutocompleteSystem {
static class Node {
HashMap<Character, Node> map;
int times = 0;
Node(int times) {
this.times = times;
map = new HashMap<Character, Node>();
}
}
static class Entry {
String str;
int times;
Entry(String str, int times) {
this.str = str;
this.times = times;
}
}
static class Trie {
Node root = new Node(0);
private void addWord(String word, int times) {
Node current = root;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if(!current.map.containsKey(ch)) {
current.map.put(ch, new Node(0));
}
current = current.map.get(ch);
}
current.times += times;
}
private List<Entry> search(String prefix) {
Node current = root;
for(int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if(current == null) return new ArrayList<Entry>();
else if(current.map.containsKey(ch)) {
current = current.map.get(ch);
}
else {
return new ArrayList<Entry>();
}
}
List<Entry> res = getAll(prefix, current);
return res;
}
private List<Entry> getAll(String str, Node current) {
List<Entry> res = new ArrayList<Entry>();
if(current.times > 0) {
res.add(new Entry(str, current.times));
}
for(Map.Entry<Character, Node> node: current.map.entrySet()) {
res.addAll(getAll(str + node.getKey(), node.getValue()));
}
return res;
}
}
Trie trie = new Trie();
public DesignSearchAutocompleteSystem(String[] sentences, int[] times) {
for(int i = 0; i < times.length; i++) {
trie.addWord(sentences[i], times[i]);
}
}
String prefix = "";
public List<String> input(char c) {
if(c == '#') {
//System.out.println("Adding word: "+prefix);
trie.addWord(prefix, 1);
prefix = "";
return new ArrayList<String>();
}
else {
prefix += c;
List<Entry> list = trie.search(prefix);
return reformat(list);
}
}
private List<String> reformat(List<Entry> list) {
List<String> res = new ArrayList<String>();
Collections.sort(list, new Comparator<Entry>(){
public int compare(Entry n1, Entry n2) {
int cmp = Integer.valueOf(n2.times).compareTo(n1.times);
if(cmp == 0) return n1.str.compareTo(n2.str);
return cmp;
}
});
for(int i = 0; i < Math.min(3, list.size()); i++) res.add(list.get(i).str);
return res;
}
}
/**
* Your AutocompleteSystem object will be instantiated and called as such:
* DesignSearchAutocompleteSystem obj = new DesignSearchAutocompleteSystem(sentences, times);
* List<String> param_1 = obj.input(c);
*/
DesignSearchAutocompleteSystem() takes O(K * L)
input() takes O(P + Q + M * log M)
Where K is avg length of each sentences
L is total number of sentences P is length of sentence formed
Q is length of nodes in trie after sentence
M is result that we need to sort
O(C) Where
Q is total number of characters in all the sentences in an input array