'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.isEnd = False
        self.data = None
        self.rank = 0
        

class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.root = TrieNode()
        self.keyword = ""
        for i, sentence in enumerate(sentences):
            self.addRecord(sentence, times[i])

    def addRecord(self, sentence, hot):
        p = self.root
        for c in sentence:
            if c not in p.children:
                p.children[c] = TrieNode()
            p = p.children[c]
        p.isEnd = True
        p.data = sentence # current stirngs up to this node, e.g., "i lov"
        p.rank -= hot # do -= because by negating, we can sort as ascending order later
    
    def dfs(self, root):
        ret = []
        if root:
            if root.isEnd:
                ret.append((root.rank, root.data))
            for child in root.children:
                ret.extend(self.dfs(root.children[child]))
        return ret
        
    def search(self, sentence):
        p = self.root
        for c in sentence:
            if c not in p.children:
                return []
            p = p.children[c]
        return self.dfs(p)
        

    def input(self, c: str) -> List[str]:
        results = []
        if c != "#": # keyword it the string user typed
            self.keyword += c
            results = self.search(self.keyword)
        else: # end of a sentence
            self.addRecord(self.keyword, 1) # record the typed sentence 
            self.keyword = ""
        return [item[1] for item in sorted(results)[:3]]

# ["AutocompleteSystem","input","input","input","input"]
# [[],["i"],[" "],["a"],["#"]]
# Your AutocompleteSystem object will be instantiated and called as such:
obj = AutocompleteSystem(["i love you","island","iroman","i love leetcode"],[5,3,2,2])
print (obj.input("i"))
print (obj.input(" "))
print (obj.input("a"))
print (obj.input("#"))
        
    
    
    
    