Trie with DFS for wildcard search.
class WordDictionary: def init(self): self.root = {}
def addWord(self, word):
node = self.root
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['$'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '$' in node
if word[i] == '.':
for child in node:
if child != '$' and dfs(node[child], i + 1):
return True
return False
if word[i] not in node:
return False
return dfs(node[word[i]], i + 1)
return dfs(self.root, 0)
add, to search.