"""
Design a data structure that supports the following two operations:

void addWord(word)

bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example
addWord("bad")

addWord("dad")

addWord("mad")

search("pad") -> false

search("bad") -> true

search(".ad") -> true

search("b..") -> true
"""

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

class WordDictionary:
    # initialize your data structure here.
    def __init__(self):
        # Write your code here
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
        # Write your code here
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.flag = True

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
        # Write your code here
        
        def dfs(index, node):
            if index == len(word):
                return node.flag
            if word[index] in node.children:
                return dfs(index + 1, node.children[word[index]])
            elif word[index] == '.':
                for c in node.children:
                    if dfs(index + 1, node.children[c]):
                        return True
            return False
        return dfs(0, self.root)

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")

f4e0ecd3d7666a0df231868cf4beec32063eeaf8
<mask token>


class WordDictionary:

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

    def addWord(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.flag = True
    <mask token>

<mask token>


class WordDictionary:

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

    def addWord(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.flag = True

    def search(self, word):

        def dfs(index, node):
            if index == len(word):
                return node.flag
            if word[index] in node.children:
                return dfs(index + 1, node.children[word[index]])
            elif word[index] == '.':
                for c in node.children:
                    if dfs(index + 1, node.children[c]):
                        return True
            return False
        return dfs(0, self.root)

<mask token>


class TrieNode:
    <mask token>


class WordDictionary:

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

    def addWord(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.flag = True

    def search(self, word):

        def dfs(index, node):
            if index == len(word):
                return node.flag
            if word[index] in node.children:
                return dfs(index + 1, node.children[word[index]])
            elif word[index] == '.':
                for c in node.children:
                    if dfs(index + 1, node.children[c]):
                        return True
            return False
        return dfs(0, self.root)

<mask token>


class TrieNode:

    def __init__(self):
        self.children = {}
        self.flag = False


class WordDictionary:

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

    def addWord(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.flag = True

    def search(self, word):

        def dfs(index, node):
            if index == len(word):
                return node.flag
            if word[index] in node.children:
                return dfs(index + 1, node.children[word[index]])
            elif word[index] == '.':
                for c in node.children:
                    if dfs(index + 1, node.children[c]):
                        return True
            return False
        return dfs(0, self.root)

"""
Design a data structure that supports the following two operations:

void addWord(word)

bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example
addWord("bad")

addWord("dad")

addWord("mad")

search("pad") -> false

search("bad") -> true

search(".ad") -> true

search("b..") -> true
"""

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

class WordDictionary:
    # initialize your data structure here.
    def __init__(self):
        # Write your code here
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
        # Write your code here
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.flag = True

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
        # Write your code here
        
        def dfs(index, node):
            if index == len(word):
                return node.flag
            if word[index] in node.children:
                return dfs(index + 1, node.children[word[index]])
            elif word[index] == '.':
                for c in node.children:
                    if dfs(index + 1, node.children[c]):
                        return True
            return False
        return dfs(0, self.root)

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")
