Leetcode 642 Solution

class TrieNode:
    def __init__(self):
        self.cnt = 0
        self.children = {}

class TrieTree:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, sentence, times):
        node = self.root

        for ch in sentence:
            child_node = node.children.get(ch)

            if child_node is None:
                child_node = TrieNode()
                node.children[ch] = child_node

            node = child_node

        node.cnt += times

    def find_node(self, s):
        node = self.root

        for ch in s:
            child_node = node.children.get(ch)

            if child_node is None:
                return None

            node = child_node

        return node

    def find_top_three(self, node, curr_s):
        candidates = []

        def find(node, curr_s):
            if node is None:
                return

            if node.cnt > 0:
                candidates.append((-node.cnt, curr_s))

            for ch, child_node in node.children.items():
                find(child_node, curr_s + ch)

        find(node, curr_s)

        candidates.sort()

        return [candidate for _, candidate in candidates][:3]


class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.curr_s = ""

        self.trie_tree = TrieTree()

        for sentence, time in zip(sentences, times):
            self.trie_tree.insert(sentence, time)

    def input(self, c: str) -> List[str]:
        if c == '#':
            self.trie_tree.insert(self.curr_s, 1)
            self.curr_s = ""
            return []

        self.curr_s += c

        node = self.trie_tree.find_node(self.curr_s)
        return self.trie_tree.find_top_three(node, self.curr_s)



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