标准Trie仅支持精确前缀匹配，因其逐字符比对且失配即终止，无法动态处理替换、插入、删除等编辑操作；模糊匹配需在搜索时通过DFS维护编辑距离并允许路径偏离，而非修改树结构。
为什么标准 trie 不支持模糊匹配
Go 标准库没有内置 Trie，更不提供模糊匹配能力。常见手写 Trie（比如只存 rune 或 byte 节点）默认只支持精确前缀匹配——它逐字符比对，一旦失配就终止，根本不会考虑替换、插入、删除等编辑操作。模糊匹配本质是带容错的路径遍历，需要在搜索时动态允许「偏离主干」，而原始结构没预留这种分支空间。
用 DFS + 编辑距离约束实现模糊前缀搜索
核心思路不是改结构，而是改搜索方式：在原有 Trie 上做深度优先遍历，维护当前编辑距离 ed，对每个节点尝试三种操作（替换/插入/删除），仅当 ed ≤ threshold 时继续递归。注意：前缀匹配要求「查询串必须完全匹配上」，所以模糊只允许发生在查询串末尾之后（即允许多匹配几个字符），或对查询串内部做容错，但最终必须能走到某个 isEnd == true 的节点。
实操建议：
- 定义结构体字段：
children map[rune]*TrieNode、isEnd bool、可选value interface{} - 搜索函数签名类似：
func (t *Trie) FuzzySearch(query string, maxEd int) []string - 递归参数必须包含：
node *TrieNode、queryIdx int、wordSoFar string、ed int - 提前剪枝：若
ed > maxEd直接 return；若queryIdx == len(query)且node.isEnd，说明精确匹配成功，结果加入；此时还可继续走子节点（对应「插入」操作，如查"cat"匹配"category"） - 不要在每层都新建
string拼接，用[]rune+append更高效
Levenshtein 和 Damerau-Levenshtein 在 Trie 中怎么选
大多数场景用基础 Levenshtein（只允许替换、插入、删除）就够了，实现简单、边界清晰。如果业务明确需要支持相邻字符交换（比如用户把 "teh" 打成 "the"），才引入 Damerau-Levenshtein ——但这会让 DFS 状态多一维（需记录上一字符是否刚被交换过），显著增加逻辑复杂度和运行开销。Trie 本身不存储编辑信息，所有判断都在搜索时动态做，所以两种算法只影响递归分支逻辑，不影响 Trie 构建。
常见错误现象：maxEd = 1 时搜 "abc" 却返回 "abx" 和 "abcd"，但漏掉 "bac"（交换）——这就是用了纯 Levenshtein 却误以为它支持交换。
性能瓶颈和实际部署注意事项
模糊搜索天然比精确匹配慢，尤其 maxEd ≥ 2 时分支爆炸。真实服务中必须加硬限制：
- 强制设置最大
maxEd（通常 ≤ 2），并在 API 层校验，避免用户传maxEd=5导致 CPU 打满 - 对长查询串（如 > 20 字符）直接降级为精确前缀匹配，或先截断再模糊
- 缓存高频模糊查询结果（key 为
query + maxEd），但注意缓存击穿：相似 query（"go"/"goe"）不能共享 - Go 中避免在 DFS 里频繁
make([]rune, 0)，复用sync.Pool或传参复用切片
真正难的不是写通逻辑，而是控制住最坏情况下的时间波动——用户输入不可控，编辑距离的指数级分支必须靠阈值和短路来兜底。
