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:
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
Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix
Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix
Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence
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
timesNow, 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); */
No comments:
Post a Comment