Python - heap - two implementations


  • 0
    S

    Used heap object here -

    import heapq
    class HeapItem(object):
        def __init__(self, index, times, sentences):
            self.index     = index
            self.times     = times
            self.sentences = sentences
        
        def __lt__(self,other):
            greater_times   = (self.times[self.index] > self.times[other.index]) 
            equal_times     = (self.times[self.index] == self.times[other.index])
            lesser_sentence = (self.sentences[self.index] < self.sentences[other.index])
            return greater_times or (equal_times and lesser_sentence )
        
    class AutocompleteSystem(object):  
        def __init__(self, sentences, times):
            """
            :type sentences: List[str]
            :type times: List[int]
            """
            self.sentences     = sentences[:]
            self.times         = times[:]
            self.prefixes      = dict()
            self.heapobjects   = dict()
            self.current = ''
            self.result  = []
    
            for k,sentence in enumerate(sentences):
                self.heapobjects[sentence] = HeapItem(k,self.times,self.sentences)
                for i in range(len(sentence)):
                    key = sentence[:i+1]
                    if key not in self.prefixes:
                        self.prefixes[ key ] = []
                    heapq.heappush(self.prefixes[key],self.heapobjects[sentence] )
    
        def input(self, c):
            """
            :type c: str
            :rtype: List[str]
            """
            if c == '#':
                if self.current not in self.heapobjects:
                    self.heapobjects[self.current] = HeapItem(len(self.times),self.times,self.sentences)
                    self.sentences                += self.current,
                    self.times                    += 1,
                else:
                    self.times[self.heapobjects[self.current].index] += 1
                
                for i in range(len(self.current)):
                    key = self.current[:i+1]
                    if key not in self.prefixes:
                        self.prefixes[key] = [ self.heapobjects[self.current] ]
                    else:
                        if self.heapobjects[self.current] not in self.prefixes[key]:
                            self.prefixes[key]  += self.heapobjects[self.current],
                    heapq.heapify(self.prefixes[key])
                self.current = ''
                self.result  = []
            else:
                self.current += c
                if self.current in self.prefixes:
                    self.result = [ self.sentences[heapobject.index] for heapobject in heapq.nsmallest(3, self.prefixes[self.current]) ]
                else:
                    self.result = []
            return self.result
    

    Another - not so space efficient

    import heapq
    class AutocompleteSystem(object):
    
        def __init__(self, sentences, times):
            """
            :type sentences: List[str]
            :type times: List[int]
            """
            self.trie    = dict()
            self.current = ''
            self.result  = []
            for k,sentence in enumerate(sentences):
                for i in range(len(sentence)):
                    key = sentence[:i+1]
                    if key not in self.trie:
                        self.trie[ key ] = []
                    heapq.heappush(self.trie[key], [-times[k], sentence] )
            
    
        def input(self, c):
            """
            :type c: str
            :rtype: List[str]
            """
            if c == '#':
                for i in range(len(self.current)):
                    key = self.current[:i+1]
                    if key not in self.trie:
                        self.trie[key] = [ [-1, self.current] ]
                    else:
                        for item in self.trie[key]:
                            if item[1] == self.current:
                                item[0] -= 1
                                break
                        else:
                            self.trie[key]  +=  [-1, self.current],
                        heapq.heapify(self.trie[key])
                self.current = ''
                self.result  = []
                #print(self.trie)
            else:
                self.current += c
                if self.current in self.trie:                
                    self.result = [ item[1] for item in heapq.nsmallest(3,self.trie[self.current]) ]
                else:
                    self.result = []
            return self.result
    

Log in to reply
 

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