Python trie + dict + sort


  • 0
    A
    from collections import defaultdict
    
    class TrieNode(object):
        def __init__(self):
            self.children = defaultdict(TrieNode)
            self.tops = []
    
    class AutocompleteSystem(object):
        def __init__(self, sentences, times):
            """
            :type sentences: List[str]
            :type times: List[int]
            """
            self.counts = defaultdict(int)
            self.root = TrieNode()
            for i in range(len(sentences)):
                self.update(sentences[i], times[i])
            # states
            self.cur = []
            self.p = self.root
    
        def update(self, sentence, time):
            self.counts[sentence] += time
            p = self.root
            for c in sentence:
                p = p.children[c]
                if sentence not in p.tops:
                    p.tops.append(sentence)
                p.tops = sorted(p.tops, cmp = lambda x, y: self.counts[y] - self.counts[x] if self.counts[y] != self.counts[x] else -1 if x < y else 1)[:3]
            
        def input(self, c):
            """
            :type c: str
            :rtype: List[str]
            """
            if c != '#':
                self.cur.append(c)
                if self.p and c in self.p.children:
                    self.p = self.p.children[c]
                    return self.p.tops
                else:
                    self.p = None
                    return []
            self.update(''.join(self.cur), 1)
            self.cur = []
            self.p = self.root
            return []
                
    
    
    # Your AutocompleteSystem object will be instantiated and called as such:
    # obj = AutocompleteSystem(sentences, times)
    # param_1 = obj.input(c)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.