# Leetcode 642 Solution

https://leetcode.com/problems/design-search-autocomplete-system

## 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)
``````