Simple Python trie solution with O(nm) runtime complexity.


  • 0
    A
    class Trie(object):
        def __init__(self, char=None):
            self.children = {}
            self.isWord = False
            self.char = char
        
        def add_word(self, word):
            if not word:
                self.isWord = True
                return
            child = self.children.get(word[0], None)
            if child:
                child.add_word(word[1:])
            else:
                new_node = Trie(word[0])
                self.children[word[0]] = new_node
                new_node.add_word(word[1:])
    
        def find_shortest(self, word, i):
            if i >= len(word) or self.isWord:
                return i
            child = self.children.get(word[i], None)
            if child:
                return child.find_shortest(word, i + 1)
            else:
                return None
    
    class Solution(object):
        def replaceWords(self, dict, sentence):
            root = Trie()
            words = sentence.split(" ")
            for word in dict:
                root.add_word(word)
            for i in range(len(words)):
                curr_word = words[i]
                root_index = root.find_shortest(curr_word, 0)
                words[i] = curr_word[:root_index]
            return ' '.join(words)

Log in to reply
 

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