Wildcard and Regex Search in a Trie
Support '.' wildcard matching by fanning out to all children at that depth, solving the design-add-and-search-words-data-structure problem.
The Wildcard Search Problem
Standard trie search handles exact characters. Wildcard search adds a special character '.' that matches any single character. When encountering a '.' during search, instead of following one specific child, we must try all children — a fan-out. This is the core idea behind LeetCode 211 'Design Add and Search Words Data Structure'. Each '.' multiplies the search paths by the number of children at that level.
Recursive Wildcard Search
Implement wildcard search with a recursive DFS helper. For each character in the pattern: if it is a literal character, follow the specific child (or return False if missing); if it is '.', recurse into all children and return True if any succeeds. At the end of the pattern, return node.is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # FalseAll lessons in this course
- TrieNode Class: Insert and Search
- Prefix Search and Starts-With
- Wildcard and Regex Search in a Trie
- Word Search II: Trie + Backtracking on Grid