# Prefix Tree (DPS + hashmap)
#  - time: O(n) # n is the length of the string
#  - space: O(t) # t is the total number of TrieNodes created in the Trie
class TreeNode(object):
    def __init__(self):
        self.end = False
        self.children = {}


class Trie(object):

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

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TreeNode()
            cur = cur.children[c]
        cur.end = True

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.end

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

class TreeNode(object):
    def __init__(self):
        self.children = {}
        self.end = False

# Prefix Tree (DPS + hashmap)
#  - time: O(n) for addWord, O(Σ^n) for search  # n is the length of the string。Σ 是字符集，这道题中的字符集为全部小写英语字母，∣Σ∣=26。
#  - space: O(∣T∣⋅∣Σ∣)，其中 ∣T∣ 是所有添加的单词的长度之和，Σ 是字符集，这道题中的字符集为全部小写英语字母，∣Σ∣=26。
class WordDictionary(object):

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

    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TreeNode()
            cur = cur.children[c]
        cur.end = True

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """

        def dfs(j, root):
            cur = root
            for i in range(j, len(word)):
                c = word[i]
                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.end

        return dfs(0, self.root)