Using trie - python


  • 0
    S
    class Solution(object):
        def replaceWords(self, roots, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
    
            class TrieNode(object):
                def __init__(self):
                    self.word = False
                    self.children = dict()
    
            class Trie(object):
                def __init__(self):
                    self.root = TrieNode()
    
                def addWord(self, word):
                    if word:
                        cur = self.root
                        for c in word:
                            if c not in cur.children:
                                cur.children[c] = TrieNode()
                            cur = cur.children[c]
                        cur.word = True
    
                def getRoot(self, word):
                    ans = ""
                    cur = self.root
                    for c in word:
                        if c in cur.children:
                            ans += c
                            cur = cur.children[c]
                            if cur.word == True:  # found smallest root!
                                return ans
                        else:
                            break
                    return word
    
            trie = Trie()
            for word in roots:
                trie.addWord(word)
    
            ans = []
            for word in sentence.split():
                ans.append(trie.getRoot(word))
            return ' '.join(ans)

Log in to reply
 

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