Python 5-line solution (using trietree)


  • 0
    class Trie:
        def __init__(self):
            self.tree = dict()
    
        def add(self, word):
            tree = self.tree
            for c in word:
                if c in tree:
                    tree = tree[c]
                    if '\0' in tree:
                        return
                else:
                    tree[c] = dict()
                    tree = tree[c]
            tree['\0'] = word
    
        def search(self, word):
            tree = self.tree
            for c in word:
                if c in tree:
                    tree = tree[c]
                    if '\0' in tree:
                        return tree['\0']
                else:
                    break
            return word
    
    class Solution:
        def replaceWords(self, words, sentence):
            trie = Trie()
            for word in words:
                trie.add(word)
            return ' '.join(trie.search(word) for word in sentence.split(' '))
    

Log in to reply
 

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