如何让字典树支持通配符匹配（'.' 匹配任意字符）？

简化版

普通 Trie 查找是「一个字符走一步」，遇到通配符 .（匹配任意一个字符）时，因为不知道该走哪个分支，就要对当前节点的所有子节点都尝试一遍——用 DFS + 回溯。普通字符仍是确定地走一步；只有遇到 . 才「分叉尝试所有孩子」。这是 LeetCode「添加与搜索单词」（WordDictionary）的经典解法。

详细版

设计一个支持 search 里带 . 的字典：

boolean search(String word) {
    return dfs(word, 0, root);
}
boolean dfs(String word, int i, Trie node) {
    if (node == null) return false;
    if (i == word.length()) return node.isEnd;   // 到末尾，看是否完整单词
    char c = word.charAt(i);
    if (c == '.') {
        // 通配符：尝试所有存在的子节点
        for (Trie child : node.children) {
            if (child != null && dfs(word, i + 1, child)) return true;
        }
        return false;
    } else {
        // 普通字符：确定地走这一个分支
        return dfs(word, i + 1, node.children[c - 'a']);
    }
}

普通字符：只走对应的那一个孩子（确定路径）。
. 通配符：对每一个非空子节点递归尝试，任一成功即成功。
到达字符串末尾时，仍要检查 isEnd（必须是完整单词，不能只是前缀）。

完整版教学

一、为什么要回溯

普通 Trie 查找是「确定性」的——每个字符唯一决定走哪条边，一路走到底，O(L)。但通配符 . 打破了确定性：它能匹配任意一个字符，所以站在某个节点、遇到 . 时，不知道该走哪个孩子，只能每个都试。一旦某条分支后面匹配失败，就要回溯回来试下一个孩子。这就把「一条路径的线性查找」变成了「在树上的深度优先搜索」。

二、两种字符两种处理

搜索时逐字符处理，分两种情况：

普通字母：和普通 Trie 一样，直接走 children[c-'a'] 这一个孩子。如果它为空，直接失败。不产生分叉。
通配符 .：遍历当前节点的所有非空子节点，对每个都递归匹配剩下的部分。只要有一个分支能成功匹配完整个 word，就返回 true。

所以只有 . 会引起「分叉 + 回溯」，普通字符仍然高效。

三、终止条件别忘 isEnd

当递归走到 i == word.length()（word 全部字符都匹配完了），不能直接返回 true，而要返回当前节点的 isEnd。因为「路径走通」只说明匹配的是某个词的前缀，必须 isEnd=true 才代表匹配到了一个完整单词。这和普通 Trie 的 search 一样，是易漏点。

四、复杂度

不含通配符：O(L)，和普通查找一样。
含通配符：最坏情况所有字符都是 .，每一层都要遍历所有孩子，复杂度可达 O(26^L) 或更实际地说 O(N × L)（N 为单词数）。. 越多、越靠前，分支越爆炸。
所以通配符查找比普通查找慢得多，. 的数量和位置直接影响性能。

五、优化与延伸

前缀确定部分先走：. 出现前的确定字符先线性走到位，缩小搜索起点。
* 通配符（匹配任意长度）：更复杂，要在「匹配 0 个 / 匹配多个」之间回溯，类似正则/通配符文件匹配，本质是带 Trie 的 DFS + 更多分支。
大量通配符查询的场景，可能改用其它索引结构（如后缀自动机、正则引擎）。

六、常见误区与追问

考点	正确口径
普通字符	按对应孩子继续走
通配符 `.`	尝试当前节点所有孩子
终止	模式耗尽时检查 `isEnd`

dfs(node, i):
  if i == len(pattern): return node.isEnd
  if pattern[i] == '.': try all children
  else: follow exact child

通配符匹配让 Trie 从单一路径查询变成回溯搜索。

误区：. 可以直接跳过一个字符。 它匹配任意一个字符，必须消耗模式中的这一位并走向某个孩子。
误区：遇到通配符只试一个孩子。 必须尝试所有非空孩子，只要有一条路径成功就匹配成功。
误区：模式走完就一定匹配。 还要检查当前节点 isEnd，否则只匹配到某个单词前缀。
追问：最坏复杂度是多少？ 通配符很多时会展开大量分支，最坏接近字符集分支数的指数级。
追问：如何剪枝？ 缺少对应孩子立即失败，也可维护子树单词长度范围等辅助信息。
追问：和正则表达式有什么区别？ 这里的 . 通常只表示单字符通配，不包含 *、分组等完整正则语义。

七、加强记忆

Trie 支持通配符 .：普通字符确定走一个孩子，遇到 . 就遍历所有非空子节点递归尝试（DFS + 回溯），任一成功即成功。到 word 末尾要检查 isEnd（必须是完整单词）。不含通配符时 O(L)；. 越多分支越爆炸（最坏 O(26^L)/O(N×L)）。这是 WordDictionary（添加与搜索单词）的经典解法。

简化版

详细版