Trie 中的通配符与正则搜索
通过在相应深度扩展到所有子节点来支持“.”通配符匹配，解决设计添加和搜索单词数据结构问题。
Trie 中的通配符与正则搜索 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
通配符搜索问题
标准字典树的 search 处理精确字符。通配符搜索增加了特殊字符 '.'，它可以匹配任意单个字符。在 search 过程中遇到 '.' 时，不能再沿着某一个特定子节点继续，而必须尝试所有子节点，也就是进行分支扩展。这正是 LeetCode 211“设计添加和搜索单词的数据结构”的核心思想。每个 '.' 都会按照该层的子节点数量成倍增加搜索路径。
递归通配符搜索
使用递归的 DFS 辅助函数实现通配符搜索。对于模式中的每个字符：如果它是字面字符，就沿着对应的子节点继续（如果子节点不存在则返回假值）；如果它是 '.'，就递归尝试所有子节点，只要有一个成功就返回真值。模式处理完毕后，返回 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')) # False为何使用任一判断进行分支扩展
遇到 '.' 时，我们调用 any(dfs(child, i+1) for child in node.children.values())。这个用于判断任一结果的生成器具有短路特性：只要某个子节点返回真值，它就会立即停止。这样可以避免不必要的探索。在最坏情况下（模式完全由 '.' 组成），我们必须探索所有路径，复杂度为 O(26^k)，其中 k 是点号的数量，因此对于大型字典树，像 '....' 这样的模式开销很大。
使用队列进行迭代式通配符搜索
迭代方法使用一个由 (node, index) 对组成的队列，从 (root, 0) 开始。对于每一对元素，如果 index == len(word) 且 node.is_end，就返回真值。否则，处理当前字符：如果是 '.'，则将所有子节点加入队列；如果是字面字符，则只将匹配的子节点加入队列。这本质上是在字典树路径上执行 BFS。
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')通配符搜索的复杂度分析
对于不含通配符的模式，search 的复杂度为 O(m)。对于包含 k 个通配符的模式，最坏情况为 O(26^k × m)，也就是关于通配符数量呈指数增长。实际应用中，通配符通常比较稀疏，而且字典树的深度较小，因此性能通常可以接受。对于完全由通配符组成的模式（例如匹配长度为 k 的所有单词），算法会退化为完整的字典树遍历。
超越单字符通配符的正则表达式搜索
扩展到完整的正则表达式（例如使用 '*' 匹配零个或多个字符）需要采用不同的处理方式。'*' 可以匹配任意后缀，因此遇到它时，必须从当前节点开始尝试所有字典树路径。在字典树中实现真正的正则表达式匹配较为复杂，通常需要使用 NFA/DFA 构造。面试中，单字符通配符（'.'）通常才是标准模式。
通配模式匹配
使用 '?'（任意单个字符）和 '*'（包括空序列在内的任意序列）进行通配模式匹配时，可以使用 DP 实现。如果在字典树中实现，'?' 对应单层分支扩展（类似 '.'），而 '*' 对应多层 DFS。组合 DP 方法定义为：dp[i][j] = 当且仅当 pattern[0..i] 匹配 string[0..j] 时为真值。面试官通常会明确要求实现哪一种变体。
实际应用：IP 地址路由
通配符字典树用于IP 路由表，其中 '*' 充当前缀通配符。路由器会存储类似 '192.168.*' 的路由前缀，并匹配传入的地址。最长前缀匹配（即最具体的路由优先）通过尽可能深入地遍历字典树，并使用最后一次发现的匹配来实现。这是字典树前缀操作和通配符操作在现实世界中的应用。
优化：剪枝无效分支
当字典树节点没有子节点（即叶节点），且结束标记为假值时，任何到达该节点的 search 操作都会返回假值。在通配符搜索过程中，如果在递归前跳过这些无效节点，就可以剪掉不必要的调用。在每个节点中维护子树包含的单词总数，还可以在没有单词符合剩余模式长度限制时，跳过整个子树。
完整的 WordDictionary 类（面试可用）
这是一个简洁、适合面试的 WordDictionary 类，将插入和点号通配符搜索结合在一起。这正是 LeetCode 211 所要求的实现。递归 search 配合具有短路特性的任一判断，代码简洁，并且能清晰展示分支扩展逻辑。
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.')) # False使用 setdefault 构建紧凑字典树
dict.setdefault(key, default) 在键存在时返回该键对应的值，否则插入 default 并返回它。在插入操作中使用 node.setdefault(c, {}) 可以省去 if-else 检查：如果子节点字典不存在，就创建它；无论是否新建，都会返回该字典。这样，插入操作就可以写成单行遍历：for c in word: node = node.setdefault(c, {})。代码简洁，也符合该语言的惯用风格。
快速检查
检验您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课您学习了：通配符 '.' 需要在匹配位置使用递归 DFS 扩展到所有子节点；生成器配合任一判断可以通过短路求值提前终止；以及setdefault 可以用单行代码完成紧凑的字典树插入。接下来，我们将结合字典树和回溯，解决单词搜索 II——在二维棋盘上同时查找多个单词。
常见问题解答
「Trie 中的通配符与正则搜索」课时是免费的吗？
是的 — 「Trie 中的通配符与正则搜索」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「Trie 中的通配符与正则搜索」这节课中我会学到什么？
通过在相应深度扩展到所有子节点来支持“.”通配符匹配，解决设计添加和搜索单词数据结构问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「Trie 中的通配符与正则搜索」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- TrieNode 类：插入与搜索
- 前缀搜索与 Starts-With
- Trie 中的通配符与正则搜索
- 单词搜索 II：Trie + 网格回溯