大家好，在leetcode的問題中有一個主題被稱為Design。這類型的問題比較像是要模擬實作出某些系統中的核心功能。今天要來分享和上一個主題Trie有關的Design問題。

Leetcode 642. Design Search Autocomplete System

題目敘述：
設計一個擁有使用者在輸入關鍵字時會自動提示功能的搜尋引擎。

• 使用者會至少輸入一段文字（至少一個字），並且以'#'來代表使用者輸入完畢
• 在一開始時，會得到sentences這個list，用來代表所蒐集到的歷史搜尋紀錄，以及與之相對的times，代表搜尋過的次數。
• 使用者每輸入一個字，就會自動去檢視符合目前使用輸入的prefix的歷史紀錄，並且列出前三高最常被搜尋的紀錄。搜尋紀錄的排序方式：是先按造times中的歷史搜尋次數，如果搜尋次數相同時，以ASCII-code較小的排在前面。
• 如果找到的符合紀錄少於三個的話，就回傳找到的所有回傳紀錄（也需要排序）。
• 最後我們要將這次的搜尋紀錄，紀錄起來。

Example1:

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"], [], []]

解釋：
使用者輸入"i"後，程式判斷出"i love you"符合並且有5次搜尋紀錄，所以排最前面；"island"有3次排第二；"iroman"和"i love leetcode"都出現過兩次，所以要比較"i"後面的字元的ASCII-code："r"和" "，因為空格的ASCII-code比較小，所以排在第三個的是"i love leetcode"。

分析：

• 我們需要去保存已知的搜尋紀錄，以及未來使用者輸入後可能的新的搜尋紀錄。因為會根據使用的輸入(prefix)來判斷有哪些搜尋紀錄（字串）是符合的，所以利用Trie來儲存。
• 在我們依序將字元儲存到Trie節點中時，要在最後一個節點後的節點的變數中儲存整個字串的內容(content)。
• 我們需要有一張hashmap去紀錄這些搜尋紀錄對應的搜尋次數。
• 有一個函數startWith可以根據目前的prefix去找尋出可能符合的字串的第一個字元的節點。
• 我們需要從這個字元開始去做dfs，來走到每一個節點路徑的終點(finished)來load出每個字串的內容，將這些內容搭配hashmap中對應的次數放入到Maximum Heap中。
• 從Maximum Heap依序將搜尋次數比較高的內容pop出來，然後用一個對應到搜尋次數的defaultdict(list)，key:list pair，來接住他們，在此之前比對現在pop出來的內容的搜尋次數是否和前一個一樣，如果一樣的話，我們需要去將對應到這個搜尋次數的list以字元的ASCII來重新排序。
  • 如果pop出來的搜尋次數和前一個不同或是沒有前一個，就將（內容, 搜尋次數）放到一個名為res的list中；同時也要用以搜尋次數為key，對應到list來將內容加入到list中。
  • 如果pop出來和前者的搜尋次數一樣，就要重新以ascii-code去排列hashmap中key為此搜尋次數所對應的list of content。再根據這個list中所擁有的內容去取代對應到相同位置的res中，或是在res長度不滿三個的情況並且list的長度夠長來去新增res中的內容。

class TrieNode:
    def __init__(self):
        self.finished = False
        self.content = ""
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.sentenceCount = {}
    
    def add(self, sentence, time):
        self.sentenceCount[sentence] = time

        curr = self.root
        for s in sentence:
            if s not in curr.children:
                curr.children[s] = TrieNode()
            curr = curr.children[s]
        
        curr.finished = True
        curr.content = sentence
    
    def startWith(self, prefix):
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return None
            curr = curr.children[c]
        
        return curr

class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.sys = Trie()
        for sentence, time in zip(sentences, times):
            self.sys.add(sentence, time)

        self.prefix = ""

    def input(self, c: str) -> List[str]:
        if c == '#':
            if self.prefix in self.sys.sentenceCount: 
                self.sys.sentenceCount[self.prefix] += 1
            else:
                self.sys.add(self.prefix, 1)
            self.prefix = ""
            
            return []

        self.prefix += c
        node = self.sys.startWith(self.prefix)
        if not node:
            return []
        
        h = []
        res = deque()

        def dfs(root):            
            if root.finished:
                heapq.heappush(h, (-1 * self.sys.sentenceCount[root.content],root.content))
            
            if len(root.children) == 0:
                return            
            
            for c in root.children:
                dfs(root.children[c])
        
        
        dfs(node)
        prev, order = None, defaultdict(list)
        while h:
            num, sentence = heapq.heappop(h)
            
            if res and prev == num:
                self.compete(num, sentence, order)
                for i, (_, hot) in enumerate(res):
                    if hot == -num:
                        
                        for j in range(len(order[num])):
                            if i + j < len(res):
                                res[i + j] = (order[num][j], -num)
                            elif len(res) < 3:
                                res.append((order[num][j], -num))
                        
                        break

            elif not res or (len(res) < 3 and prev != num):
                res.append((sentence, -num))
                prev = num
                order[num].append(sentence)
        # print(self.sys.sentenceCount)
        

        return [s for s, _ in res]
                
    
    def compete(self, num, sentence, order):
        order[num].append(sentence)
        order[num].sort(key = lambda x: [ord(c) for c in x])


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

這個解法只是當下看到這個問題時最直覺的反應，然後就寫了將近百行的程式（我在leetcode中寫過最長的），目前還沒有參考其他人的解答，相信一定有更好的解法。
對了，本題僅對有leetcode premium的使用者開放，所以沒有premium的人無法在leetcode作答這題😅。