1from collections import defaultdict as dd
2
3class Node:
4 def __init__(self, l=''):
5 self.A = dd(Node)
6
7 def add_word(self, word):
8 if word:
9 self.A[word[0]].add_word(word[1:])
10
11 def search(self, word):
12 if word:
13 l = word[0]
14 if l == '.':
15 return any(self.A[l].search(word[1:]) for l in self.A)
16 return l in self.A and self.A[l].search(word[1:])
17 return word == ''
18
19
20class WordDictionary:
21
22 def __init__(self):
23 self.trie = Node()
24
25 def addWord(self, word: str) -> None:
26 self.trie.add_word(word+'_')
27
28 def search(self, word: str) -> bool:
29 return self.trie.search(word+'_')