Python DFS and Trie

  • 0
    import collections
    class TrieNode():
        def __init__(self):
            self.children = collections.defaultdict(TrieNode)
            self.is_word = False
    class WordDictionary(object):
        def __init__(self):
            Initialize your data structure here.
            self.root = TrieNode(
        def addWord(self, word):
            Adds a word into the data structure.
            :type word: str
            :rtype: void
            node = self.root
            for w in word:
                node = node.children[w]
            node.is_word = True
        def search(self, word):
            Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
            :type word: str
            :rtype: bool
            def dfs(word,node):
                if not word: return node.is_word
                if word[0] in node.children:
                    return dfs(word[1:],node.children[word[0]])
                elif word[0]=='.':
                    return any(dfs(word[1:],node.children[i]) for i in node.children)
                else: return False
            return dfs(word,self.root)

Log in to reply

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