Simple Python Solution


  • 0
    M
    class TrieNode:
        
        def __init__(self):
            self.root = None
            self.children = dict()
        
        def insert(self, root):
            node = self
            
            for char in root:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            
            node.root = root
                
        def replace(self, word):
            node = self
            
            for char in word:
                if char not in node.children:
                    return word
                node = node.children[char]
                if node.root:
                    return node.root
            
            return word
    
    
    class Solution(object):
        def replaceWords(self, dict, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
    
            trie = TrieNode()
            for root in dict:
                trie.insert(root)
                
            return ' '.join(map(trie.replace, sentence.split()))
    

Log in to reply
 

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