title
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary()初始化词典对象void addWord(word)将word添加到数据结构中，之后可以对它进行匹配bool search(word)如果数据结构中存在字符串与word匹配，则返回true；否则，返回false。word中可能包含一些'.'，每个.都可以表示任何一个字母。
示例：
输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
提示：
1 <= word.length <= 500addWord中的word由小写英文字母组成search中的word由 ‘.’ 或小写英文字母组成- 最多调用
50000次addWord和search
solution
class TrieNode:
def __init__(self):
self.precount = 0
self.count = 0
self.children = {}
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.precount += 1
node.count += 1
def dfs(self, node, word):
if word == "":
return node.count > 0
a = word[0]
if a == ".":
for k, v in node.children.items():
if self.dfs(v, word[1:]):
return True
return False
else:
if a not in node.children:
return False
return self.dfs(node.children[a], word[1:])
return False
def search(self, word: str) -> bool:
node = self.root
return self.dfs(node, word)