642 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 '#').

You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the 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 hot degree, use ASCII-code order (smaller one appears first).
• If less than 3 hot sentences exist, 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.

Implement the AutocompleteSystem class:

• AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
• List<String> input(char c) This indicates that the user typed the character c.
• Returns an empty array [] if c == '#' and stores the inputted sentence in the system.
• Returns the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.

Example 1:

Input
["AutocompleteSystem", "input", "input", "input", "input"]
[
    [
        ["i love you", "island", "iroman", "i love leetcode"],
        [5, 3, 2, 2]
    ], 
    ["i"], [" "], ["a"], ["#"]
]
Output
[
    null,
    ["i love you", "island", "i love leetcode"],
    ["i love you", "i love leetcode"],
    [],
    []
]

Explanation
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]. 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.
obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ".
obj.input("a"); // return []. There are no sentences that have prefix "i a".
obj.input("#"); // return []. 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.

Constraints:

• n == sentences.length
• n == times.length
• 1 <= n <= 100
• 1 <= sentences[i].length <= 100
• 1 <= times[i] <= 50
• c is a lowercase English letter, a hash '#', or space ' '.
• Each tested sentence will be a sequence of characters c that end with the character '#'.
• Each tested sentence will have a length in the range [1, 200].
• The words in each input sentence are separated by single spaces.
• At most 5000 calls will be made to input.

 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

class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        # Build trie
        self.root = {}
        for i, s in enumerate(sentences):
            self._add_sentence(s, count=times[i])

        self.path = []
        self.current = self.root

    def _add_sentence(self, s: str, count: Optional[int]=None):
        cur = self.root
        for c in s:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur['count'] = count if count else cur.get('count', 0) + 1
        
    def _dfs(
        self,
        trie: Dict[str,Dict],
        path: List[str],
        res: List[str]
    ) -> None:
        if not trie:
            return
        if 'count' in trie:
            res.append((-trie['count'], ''.join(path)))
        for k in trie.keys():
            if k == 'count':
                continue
            self._dfs(trie[k], path+[k], res)
    
    def input(self, c: str) -> List[str]:
        if c == '#':
            self._add_sentence(''.join(self.path))
            self.path = []
            self.current = self.root
            return []
        self.path.append(c)
        if c not in self.current:
            self.current = {}
            return []
        self.current = self.current[c]
        res = []
        self._dfs(self.current, self.path, res)
        return [i[1] for i in sorted(res)[:3]]


# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)