找出编辑距离不大于 K 的单词
内容提要
本文介绍用Trie结合DFS查找字典中与给定单词编辑距离不超过K的词。相比逐个计算编辑距离的O(NL²)方法，该算法按匹配、替换、增加、删除四种情况递归搜索，并只枚举当前节点字母以优化性能。在23万词字典上测试，CPython约2.5秒，PyPy约1.6秒。
延伸解读
Trie+DFS 为何能降低复杂度
文章指出，逐个计算编辑距离的总时间复杂度为 O(NL²)，其中 N 为字典词数，L 为平均词长。而基于 Trie 的 DFS 方法利用前缀共享，只沿可能匹配的分支递归，避免了对每个词独立做二维 DP。这种剪枝在字典很大时优势明显，因为大量前缀不匹配的词会被提前跳过，实际访问的节点数远小于 N。
递归终止条件与易漏细节
函数只在 tol 为 0 时终止，而不是 word 为空时。原因是剩余编辑距离可以全部用于增加后缀，使字典词比查询词更长。此外，匹配当前字符时，若 word 已结束，也需视为不匹配并消耗一次编辑距离。这些细节在实现中容易忽略，却直接影响结果正确性。
枚举当前节点字母的优化
在“增加任意字母”分支中，文章没有枚举全部 26 个字母，而是只枚举当前 Trie 节点的所有子节点字母。因为只有这些字母才可能构成字典中的词，其余字母会立即走入死路。这一改动由 Jayxon 提出，减少了大量无效递归，是性能提升的关键之一。
实测性能与适用场景
在约 23.6 万词的 /usr/share/dict/words 字典上，对一句包含多个拼写错误的文本查询，CPython 耗时约 2.5 秒，PyPy 约 1.6 秒。这说明该方法在单次或少量查询时表现良好，但若查询量极大，仍需考虑缓存或更进一步的索引优化。文章也提到 Lee Shellay 后续更新了更优实现。
Q&A
如何高效找出字典中与给定单词编辑距离不超过K的所有单词？
可以基于字典构建Trie（前缀树），然后使用DFS递归搜索。在搜索过程中，根据匹配、替换、增加、删除四种操作更新剩余可容忍的编辑距离tol，并只枚举当前Trie节点的字母来优化性能。
为什么用Trie+DFS比直接计算编辑距离更快？
直接计算每个单词的编辑距离需要O(NL²)的时间复杂度（N为字典大小，L为平均单词长度），而Trie+DFS通过共享前缀和剪枝（tol限制）大幅减少计算量，尤其适合多次查询。
Trie+DFS算法中，递归终止的条件是什么？
当剩余可容忍的编辑距离tol为0时终止。注意不是word为空时终止，因为可能还有编辑距离用于增加后缀。
在Trie+DFS算法中，如何处理“增加字母”的情况？
增加字母时，枚举当前Trie节点的所有子节点字母（而不是枚举26个字母），然后递归调用，同时将tol减1。
Trie+DFS算法在大型字典上的性能如何？
在包含235886个单词的字典上测试，CPython运行约2.53秒，PyPy约1.63秒。
如何构建用于编辑距离搜索的Trie？
遍历字典中的每个单词，将字符逐个插入Trie节点，并在单词结束时添加结束符（如'$'）标记单词结束。
