Python DFS and Trie


  • 0
    A
    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.