原題

設(shè)計一個包含下面兩個操作的數(shù)據(jù)結(jié)構(gòu)：addWord(word), search(word)
addWord(word)會在數(shù)據(jù)結(jié)構(gòu)中添加一個單詞。而search(word)則支持普通的單詞查詢或是只包含. 和a-z的簡易正則表達(dá)式的查詢。一個 . 可以代表一個任何的字母。

樣例

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

解題思路

• 本題跟Implement Trie十分相似，同樣需要使用字典樹
• 由于本題里中'.'可以代替任意字符，所以當(dāng)某一個字符是'.'，就需要查找所有的子樹，只要有一個最終能夠存在，就返回True

完整代碼

class TrieNode(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.children = {}
        self.IsWord = 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 letter in word:
            child = node.children.get(letter)
            if child is None:
                child = TrieNode()
                node.children[letter] = child
            node = child
        node.IsWord = 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
        """
        return self.find(self.root, word)
        
    def find(self, node, word):
        if word == "":
            return node.IsWord
        if word[0] == ".":
            for x in node.children:
                if self.find(node.children[x], word[1:]):
                    return True
        else:
            child = node.children.get(word[0])
            if child:
                return self.find(child, word[1:])
        return False