Iterative python solution using trie


  • 1
    T
    class TrieNode(object):
        def __init__(self):
            self.count = 0
            self.children = {}
    
    class WordDictionary(object):
        def __init__(self):            
            self.root = TrieNode()
    
        def addWord(self, word):            
            node = self.root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.count += 1
            
    
        def search(self, word):
            nodes = [self.root]
            for ch in word:
                subNodes = []
                for anode in nodes:
                    if ch == '.':
                        subNodes += anode.children.values()
                    elif ch in anode.children:
                        subNodes.append(anode.children[ch])
                nodes = subNodes
            for anode in nodes:
                if anode.count > 0:
                    return True
            return False

Log in to reply
 

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