如何用 Trie 实现只修改一个字符的 Magic Dictionary？

简化版

把词典单词插入 Trie。查询时做 DFS，状态包含当前位置和已经修改的字符数 diff；普通分支可以走相同字符，若 diff==0 还可以尝试其他字符分支。最后只有走到单词结尾且 diff==1 才返回 true。

详细版

Magic Dictionary 的典型要求是：给一个查询词，判断词典中是否存在某个单词，它与查询词长度相同，并且恰好只有一个字符不同。

Trie 做法：

建 Trie 存所有词典单词。
搜索时递归参数为 (node, index, diff)。
对当前位置字符 ch：
- 走相同孩子，diff 不变。
- 若 diff==0，可以走任意不同孩子，diff+1。
到达查询词末尾时，必须 node.isEnd && diff == 1。

boolean dfs(Trie node, String word, int i, int diff) {
    if (i == word.length()) return node.isEnd && diff == 1;
    int target = word.charAt(i) - 'a';
    for (int c = 0; c < 26; c++) {
        Trie child = node.children[c];
        if (child == null) continue;
        int ndiff = diff + (c == target ? 0 : 1);
        if (ndiff <= 1 && dfs(child, word, i + 1, ndiff)) return true;
    }
    return false;
}

重点是“恰好一次修改”，不是零次，也不是最多一次。

完整版教学

一、题目里的“修改一次”是什么意思

Magic Dictionary 通常只允许替换一个字符，不允许插入或删除字符。因此候选词必须和查询词长度相同。例如词典有 hello，查询 hhllo 返回 true，因为只改第 2 个字符；查询 hello 返回 false，因为没有修改；查询 hell 也返回 false，因为长度不同。

dict = [hello, leetcode]

search("hhllo")  -> true   hello 差 1 个字符
search("hello")  -> false  差 0 个字符
search("hell")   -> false  长度不同，不是替换一次

这个“恰好一次”是最常见坑。很多人写成“最多一次不同”，会把完全相同的单词误判为 true。

二、Trie 搜索状态为什么要带 diff

普通 Trie search 的状态只有当前节点和字符下标，因为每一位必须完全相同。Magic Dictionary 允许一次不同，所以搜索状态还要记录已经用了几次修改。diff=0 表示还没改过，可以尝试不同分支；diff=1 表示修改机会已用完，后面必须完全匹配。

query = hhllo
dict path = hello

h == h: diff=0
h != e: diff=1
l == l: diff=1
l == l: diff=1
o == o: diff=1
末尾 isEnd 且 diff=1 -> true

如果某条路径让 diff 超过 1，就可以立刻剪枝，因为它已经不可能满足“只修改一个字符”。

三、为什么结尾必须检查 diff==1

到达查询词末尾时，node.isEnd 只说明词典中存在同长度路径；diff==1 才说明它与查询词恰好差一个字符。两个条件缺一不可。如果只检查 isEnd，相同单词会误判；如果只检查 diff==1，路径不是完整单词也会误判。

dict = [abc, abcd]
query = abc

路径 abc 存在，isEnd=true
diff=0
结果应 false，因为没有修改任何字符

这和通配符 Trie 的终止条件类似：走完路径不等于命中完整单词，必须看终止标记；本题还要额外看差异次数。

四、DFS 分支如何控制复杂度

每一层最多尝试 26 个孩子，但只有在 diff==0 时不同字符分支才有意义。一旦已经修改过，后面只能继续走相同字符分支，否则 diff 会超过 1。实际分支远小于“每层 26 个都展开”。

长度 L=5
允许 1 次不同：
  可以选择 5 个位置作为修改点
  修改点尝试最多 25 个不同字符
大致候选上界约 L * 25，而不是 26^L

Trie 还能利用词典中实际存在的孩子剪枝：不存在的字符分支根本不遍历。对于稀疏词典，这个剪枝很有效。

五、和生成所有变体查哈希表的对比

另一种做法是把查询词每一位替换成其他 25 个字符，生成候选词去哈希表查。若单词长度为 L，字符集为 26，每次查询最多生成 25*L 个候选。这个方法简单，但会构造大量字符串。

方案	思路	查询复杂度	特点
生成变体 + 哈希	枚举所有一位替换	`O(25L构串成本)`	简单
Trie + DFS	在词典树中尝试一次分叉	与实际分支相关	少构造字符串
按长度分组比较	扫同长度词	`O(M*L)`	词多时慢

面试中 Trie 方案更能体现“搜索空间剪枝”。哈希变体法也可以作为对比补充，说明你知道多种解法。

常见误区与追问

记忆钩子：Magic Dictionary 的 magic 是“恰好改一次”，结尾要同时满足完整单词和 diff==1。

误区：完全相同的单词也返回 true。 题目要求修改一个字符，差异为 0 应返回 false。
误区：允许插入或删除字符。 经典 Magic Dictionary 只允许替换一个字符，长度必须相同。
误区：DFS 中不同分支可以多次走。 一旦 diff==1，再走不同字符就超过限制，必须剪枝。
追问：能用哈希表做吗？ 能，生成所有一位替换候选查 set；Trie 避免大量构造字符串。
追问：为什么末尾还要看 isEnd？ 路径存在可能只是某个长词前缀，必须确认完整单词。
追问：字符集不是 26 个怎么办？ 用 Map 孩子遍历实际分支，复杂度和实际字符集有关。

加强记忆

Magic Dictionary 可以记成“带差异次数的 Trie 搜索”。普通字符匹配时沿相同分支走，尚未修改时可以尝试一个不同分支，并把 diff 从 0 变成 1；之后必须完全匹配。走到末尾时，只有 isEnd=true 且 diff==1 才成功。把“恰好一次替换”和“完整单词结尾”两个条件同时记住，就不会把相同单词、前缀路径或长度不同的词误判。

简化版

详细版