Python solution recursive version (DFS)

  • 12

    class TrieNode(object):

    def __init__(self):
        self.word = False
        self.children = {}

    class WordDictionary(object):

    def __init__(self):
        self.root = TrieNode()
    def addWord(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.word = True
    def search(self, word):
        return self.searchFrom(self.root, word)
    def searchFrom(self, node, word):
        for i in xrange(len(word)):
            c = word[i]
            if c == '.':
                for k in node.children:
                    if self.searchFrom(node.children[k], word[i+1:]):
                        return True
                return False
            elif c not in node.children:
                return False
            node = node.children[c]
        return node.word

Log in to reply

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