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.
Wildcard and Regex Search in a Trie is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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')) # FalseWhy Use any() for Fan-Out
When a '.' is encountered, we call any(dfs(child, i+1) for child in node.children.values()). The any() generator is short-circuit — it stops as soon as one child returns True. This avoids unnecessary exploration. In the worst case (all '.' pattern), we explore all paths — complexity is O(26^k) where k is the number of dots, making patterns like '....' expensive for large tries.
Iterative Wildcard Search with Queues
An iterative approach uses a queue of (node, index) pairs. Start with (root, 0). For each pair, if index == len(word) and node.is_end, return True. Otherwise, process the current character: for '.' enqueue all children; for a literal, enqueue only the matching child. This is essentially BFS over trie paths.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')Complexity Analysis of Wildcard Search
For a pattern with no wildcards, search is O(m). For a pattern with k wildcards, worst case is O(26^k × m) — exponential in the number of wildcards. In practice, wildcards are usually sparse and the trie is shallow, so performance is acceptable. For patterns that are entirely wildcards (e.g., matching all words of length k), it degenerates to a full trie traversal.
Regex Search Beyond Single-Char Wildcards
Extending to full regex (e.g., '*' matching zero or more characters) requires different handling. A '*' can match any suffix, so when encountering it, we must try all trie paths from the current node. True regex matching in a trie is complex — usually reserved for NFA/DFA constructions. For interviews, single-character wildcards ('.') are the standard pattern.
Glob Pattern Matching
Glob matching with '?' (any single char) and '*' (any sequence including empty) can be implemented with DP. If implementing in a trie, '?' maps to single-level fan-out (like '.') and '*' maps to multi-level DFS. The combined DP approach: dp[i][j] = True if pattern[0..i] matches string[0..j]. Interviewer typically specifies which variant to implement.
Practical Application: IP Address Routing
Wildcard tries are used in IP routing tables where '*' acts as a prefix wildcard. A router stores route prefixes like '192.168.*' and matches incoming addresses. Longest-prefix matching (the most specific route wins) is implemented by traversing the trie as deep as possible and using the last seen match. This is a real-world application of trie prefix and wildcard operations.
Optimisation: Pruning Dead Branches
When a trie node has no children (leaf) and is_end = False, any search reaching it returns False. During wildcard search, skipping these dead-end nodes before recursing can prune unnecessary calls. Maintaining a word_count in each node (total words in the subtree) lets us skip an entire subtree if no words match remaining pattern length constraints.
Full WordDictionary Class (Interview-Ready)
A clean, interview-ready WordDictionary combining insert and dot-wildcard search in one class. This is the exact implementation expected for LeetCode 211. The recursive search with short-circuit any() is concise and clearly demonstrates the fan-out logic for interviewers.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # FalseUsing setdefault for Compact Trie
dict.setdefault(key, default) returns the value for key if present, otherwise inserts default and returns it. Using node.setdefault(c, {}) in insert eliminates the if-else check: it creates the child dict if missing and returns it either way. This makes insert a single-line traversal: for c in word: node = node.setdefault(c, {}). Clean and Pythonic.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: wildcard '.' requires fan-out to all children at the matching position using recursive DFS, using any() with a generator provides short-circuit evaluation for early termination, and setdefault enables a compact single-line trie insert. Next up we combine trie and backtracking to solve Word Search II — finding multiple words simultaneously on a 2D board.
Frequently asked questions
Is the “Wildcard and Regex Search in a Trie” lesson free?
Yes — the full text of “Wildcard and Regex Search in a Trie” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Wildcard and Regex Search in a Trie” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All 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