Python detailed solution using trie


  • 0
    S
    
    
    class AutocompleteSystem(object):
        class Node:
            def __init__(self):
                self.links = [None] * 27
                # store the resultant sentences prefixed with root to this node
                self.sentence_freq = collections.defaultdict(int)
    
        def __init__(self, sentences, times):
            """
            :type sentences: List[str]
            :type times: List[int]
            """
            self.root = AutocompleteSystem.Node()
            for s, n in zip(sentences, times):
                self._insert(s, n)
            self.answers = [(0, '')] * 4  # answer <- (freq, sentence)
            self.current_node = self.root
    
        def input(self, c):
            """
            :type c: str
            :rtype: List[str]
            """
            if c == '#':
                s = ''.join(self.path)
                self._insert(s)  # add the new sentence into histories
                self.current_node = self.root  # restore initial states
                return []
            else:
                self.path.append(c)
            if self.current_node is None:  # no matching sentences
                return []
            self.current_node = self.current_node.links[AutocompleteSystem._char_to_index(c)]
            if self.current_node is None:
                return []
            else:  # search possible matching sentences
                self.answers = [(0, '')] * 4
                for s, freq in self.current_node.sentence_freq.items():
                    self._add_answer((freq, s))
                return [s for freq, s in self.answers[0:3] if freq > 0]
    
        @staticmethod
        def _char_to_index(c):
            """
            Get the index for a character c in Node.links
            """
            if c == ' ':
                return 26
            return ord(c) - ord('a')
    
        @staticmethod
        def _index_to_char(i):
            """
            Get the character by the index i in Node.links.
            """
            if i == 26:
                return ' '
            return chr(ord('a') + i)
    
        def _insert(self, s, n=1):
            """
            Insert a sentence s for n times.
            """
            p = self.root
            for c in s:
                i = AutocompleteSystem._char_to_index(c)
                if p.links[i] is None:
                    p.links[i] = AutocompleteSystem.Node()
                p = p.links[i]
                p.sentence_freq[s] += n
    
    
        def _add_answer(self, answer):
            """
            Add an answer into self.answers by the specified sorting strategy.
            """
    
            def should_stand_before(ans1, ans2):
                if ans1[0] == ans2[0]:
                    return ans1[1] < ans2[1]
                return ans1[0] > ans2[0]
    
            # insertion sort
            for i in reversed(range(3)):
                if should_stand_before(answer, self.answers[i]):
                    self.answers[i + 1] = self.answers[i]
                else:
                    self.answers[i + 1] = answer
                    return
            self.answers[0] = answer  # there exists answer > answers[0] originally
    

    We may use a priority queue instead of the simple array self.answers here. However, since the problem size is quite small, a simple array with insertion sort is enough.


Log in to reply
 

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