class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class WordDictionary:
    """
    @param: word: Adds a word into the data structure.
    @return: nothing
    """

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word):
        # write your code here

        node = self.root

        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    """
    @param: word: A word could contain the dot character '.' to represent any one letter.
    @return: if the word is in the data structure.
    """

    def search(self, word):
        # write your code here
        return self.find(self.root, 0, word)

    # 对于字符串中的.我们可以递归查找
    # 关于这道问题的难点是通配符 "." 的处理，其实也不难：在遇到 "." 的时候，使用递归方法，将该结点的每一个分支都看过去，
    # 只要有一个分支返回 true 就可以了，全部分支都走过去，都没有返回 true 的才返回 false。
    def find(self, node, index, word):
        # exit
        if index == len(word):
            return node.is_word

        ch = word[index]
        # 如果当前字母是.， 那么每一个分支都要走一遍
        if ch == '.':
            for child in node.children:
                if self.find(node.children[child], index + 1, word):
                    return True
            return False
        elif ch not in node.children:
            return False
        else:
            return self.find(node.children[ch], index + 1, word)