Medium Trie + DFS Tries
In plain English: Build a word dictionary that supports wildcard searches — a dot can match any letter.
Insert works like a normal trie. Search uses DFS: for regular chars, follow the child; for '.', branch into all children. The backtracking handles wildcards naturally.
Prompt
Design a data structure that supports adding words and searching for words where '.' can match any single character.
Try to write it from scratch before scrolling down.
Solution
class WordDictionary:
def __init__(self):
self.children = {}
self.is_end = False
def add_word(self, word):
node = self
for ch in word:
if ch not in node.children:
node.children[ch] = WordDictionary()
node = node.children[ch]
node.is_end = True
def search(self, word):
return self._dfs(word, 0)
def _dfs(self, word, i):
if i == len(word):
return self.is_end
ch = word[i]
if ch == '.':
# wildcard: try every child
for child in self.children.values():
if child._dfs(word, i + 1):
return True
return False
if ch not in self.children:
return False
return self.children[ch]._dfs(word, i + 1)
# Test: d = WordDictionary()
# d.add_word("bad"); d.add_word("dad")
# d.search(".ad") == True; d.search("b..") == True
# d.search("b.") == False