Straightforward Python backtracking solution


  • 0
    S
    class WordDictionary(object):
        def __init__(self):
            """
            initialize your data structure here.
            """
            class TrieNode(object):
                def __init__(self):
                    """
                    Initialize your data structure here.
                    """
                    self.val = False
                    self.children = collections.defaultdict(TrieNode)
            self.root = TrieNode()
            
    
        def addWord(self, word):
            """
            Adds a word into the data structure.
            :type word: str
            :rtype: void
            """
            node = self.root
            for letter in word:
                node = node.children[letter]
            node.val = 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
            """
            node = self.root
            return self.backtrack(word, node)
            
        def backtrack(self, word, node):
            
            for i in range(len(word)):
                if word[i] == ".":
                    for letter in node.children:
                        if self.backtrack(word[i+1:], node.children[letter]):
                            return True
                    return False
                elif word[i] in node.children:
                    node = node.children[word[i]]
                else:
                    return False
            return node.val
                    
            
    
    # Your WordDictionary object will be instantiated and called as such:
    # wordDictionary = WordDictionary()
    # wordDictionary.addWord("word")
    # wordDictionary.search("pattern")

Log in to reply
 

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