211. Design Add and Search Words Data Structure

211. Design Add and Search Words Data Structure

這一題比較特別，需要模糊比對搜尋的字串，主要也要用到 Trie 除了紀錄自以爲，可以用特殊的字元記錄額外資訊

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.trie
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['$'] = True


    def search(self, word: str) -> bool:
        def search_in_node(word, node) -> bool:
            for i, char in enumerate(word):
                if char == '.':
                    for x in node:
                        if x != '$' and search_in_node(word[i+1:], node[x]):
                            return True
                if char not in node:
                    return False
                else:
                    node = node[char]
            return '$' in node
        return search_in_node(word, self.trie)


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