211. Design Add and Search Words Data Structure (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}

    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur = self.root
        for c in word:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur["@"] = True
        
    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        self.result = False
        def dfs(word, node):
            if not self.result:
                if not word:
                    if node.get("@"):
                        self.result = True
                else:
                    c = word[0]
                    if c == ".":
                        for k in node:
                            if k != "@":
                                dfs(word[1 : ], node[k])
                    elif c not in node:
                        return
                    else:
                        dfs(word[1 : ], node[c])
        dfs(word, self.root)
        return self.result


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)