Python: clear solution with Trie


  • 0
    S
    class Node:
        def __init__(self):
            self.is_key = False
            self.links = [None] * 26
            
    class Trie:
        def __init__(self):
            self.root = Node()
            
        def _char_to_index(self, c):
            return ord(c) - ord('a')
        
        def insert(self, key):
            p = self.root
            for c in key:
                i = self._char_to_index(c)
                if p.links[i] is None:
                    p.links[i] = Node()
                p = p.links[i]
            p.is_key = True
            
        def search_root(self, word):
            # find the shortest key which is a prefix of word
            # if not root exists, word itself is returned
            p = self.root
            root = []
            for c in word:
                i = self._char_to_index(c)
                root.append(c)
                if p.links[i] is None: # no prefix
                    return word
                p = p.links[i]
                if p.is_key:
                    return ''.join(root)
            return word
            
            
    class Solution:
        def replaceWords(self, dict, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
            trie = Trie()
            for key in dict:
                trie.insert(key)
            words = sentence.split(' ')
            for i in range(len(words)):
                words[i] = trie.search_root(words[i])
            return ' '.join(words)

Log in to reply
 

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