目录
收起
展开
题目描述 题意分析 解法：枚举替换 + 哈希集合
核心思路 解题步骤 代码实现 复杂度分析 关键点总结
易错点总结 相似题目
✅ 676. 实现一个魔法字典
要什么 ：设计一个数据结构，buildDict 一次性载入一批互不相同的单词；search(word) 回答「能否把 word 中恰好一个 字符换成另一个字符，使它变成字典里的某个单词」。约束透露的信号 ：「恰好一个」是双向的硬约束——完全相同（改动 0 处）要返回 false，差异两处以上也要返回 false。这意味着替换后的候选串必须与原串在且仅在一个位置不同 ，枚举替换时必须显式跳过「换成自己」。另外，只有替换操作，没有插入和删除，所以匹配的两个串长度必然相等 ，可以按长度先做一层筛选。字符集是小写字母共 26 个，单词数与长度都不超过 100，规模很小，允许每次查询做常数倍的枚举。边界 ：buildDict 只调用一次，之后才会有若干次 search，所以预处理可以做得重一些；字典中的单词互不相同，不必去重；单词长度可能为 1，此时唯一的位置就是全部；查询词可能根本不在字典里，也可能恰好在字典里（此时必须返回 false）。
最朴素的做法是每次查询都遍历字典里的每个单词，逐字符比较统计差异个数，恰好为 1 就返回 true。设字典有 n 个词、词长 L，单次查询是 $O(nL)$。这在本题数据下其实也能过，但它把「查字典」这件事退化成了线性扫描，没有利用「字符集只有 26 个」这个更强的条件。满足条件的字典词只有极少量候选 ——把查询词的某一位换成另一个字母，得到的串数量只有 $25L$ 个，且每一个都能直接查表判断在不在字典里。主动生成所有「与查询词恰好差一位」的候选串，逐个到哈希集合里查存在性 。候选集的规模只与词长和字符集大小有关，与字典规模完全无关。一个存放全部字典单词的哈希集合 。查询过程的不变量是：在处理第 i 位时，字符数组中除第 i 位外的所有位置都保持查询词的原始字符 ——这条不变量保证生成的每个候选与原串差异恰好为 1，也正是为什么每轮内层循环结束后必须把第 i 位复原。ch == old 来保证；上界（不能是 2 处以上）靠一次只改一位、且改完立刻复原来保证。
buildDict 把所有单词塞进哈希集合。为什么用集合而不是列表 ：查询阶段需要的是 $O(L)$ 的存在性判断（哈希一次字符串），列表只能线性查找，会把每次查询拖回 $O(nL)$。
search 先把查询词转成可变的字符数组。为什么要转数组 ：Java 的 String 和 Go 的 string 都不可变，若每次替换都用切片拼接会产生大量临时对象；转成 char[] / []byte 后只需改一个位置再整体构造一次候选串。
外层遍历位置 i，先把原字符存进 old。为什么必须先存 ：内层会反复覆盖这一位，没有备份就无法复原，也无法判断「换成的是不是自己」。
内层遍历 'a' 到 'z'，遇到 ch == old 就跳过。为什么必须跳过 ：不跳过就等于允许「改动 0 处」，查询词本身若在字典里会被误判为 true，直接违反「恰好一个」。
把第 i 位改成 ch，构造候选串查集合；命中就复原并返回 true。为什么命中也要复原 ：本题里返回后数组即被丢弃，复原不影响正确性，但保持「函数不留下副作用」是好习惯；若把字符数组提升为成员变量复用，不复原就会污染下一次查询。
内层结束后把第 i 位复原成 old，再进入下一个位置。为什么这一步是正确性的关键 ：不复原会让上一轮的改动残留，下一轮再改一位就变成「差异两处」，既可能漏判也可能错判。
全部位置试完仍无命中，返回 false。
以 buildDict(["hello", "leetcode"]) 后调用 search("hhllo") 走一遍。字符数组为 ['h','h','l','l','o']。i = 0：old = 'h'，依次把首位换成 a、b、…（跳过 h），得到 ahllo、bhllo 等 25 个候选，都不在集合里；内层结束后复原首位为 h。i = 1：old = 'h'，换成 a 得 hallo 不在集合，换成 b、c、d 均不在，换成 e 得到 hello——命中集合，复原后立即返回 true。整个过程只查了 30 次左右，与字典大小无关。再看 search("hello")：每一位都会被换成 25 个别的字母，得到的 125 个候选没有一个在字典里（hello 自己因 ch == old 被跳过），最终返回 false，这正是「不允许 0 处改动」的体现。
// 核心实现：枚举替换 + 哈希集合，维护必要状态并避免重复处理。
class MagicDictionary {
private final Set < String > set = new HashSet <>();
public void buildDict ( String [] dictionary ) {
for ( String w : dictionary ) {
set . add ( w );
}
}
public boolean search ( String searchWord ) {
char [] s = searchWord . toCharArray ();
for ( int i = 0 ; i < s . length ; i ++) {
char old = s [ i ];
for ( char ch = 'a' ; ch <= 'z' ; ch ++) {
if ( ch == old ) {
continue ;
}
s [ i ] = ch ;
if ( set . contains ( new String ( s ))) {
s [ i ] = old ;
return true ;
}
}
s [ i ] = old ;
}
return false ;
}
}
// 核心实现：枚举替换 + 哈希集合，维护必要状态并避免重复处理。
type MagicDictionary struct {
set map [ string ] struct {}
}
func Constructor () MagicDictionary {
return MagicDictionary { set : make ( map [ string ] struct {})}
}
func ( m * MagicDictionary ) BuildDict ( dictionary [] string ) {
for _ , w := range dictionary {
m . set [ w ] = struct {}{}
}
}
func ( m * MagicDictionary ) Search ( searchWord string ) bool {
b := [] byte ( searchWord )
for i := 0 ; i < len ( b ); i ++ {
old := b [ i ]
for ch := byte ( 'a' ); ch <= byte ( 'z' ); ch ++ {
if ch == old {
continue
}
b [ i ] = ch
if _ , ok := m . set [ string ( b )]; ok {
b [ i ] = old
return true
}
}
b [ i ] = old
}
return false
}
时间复杂度 ：buildDict 为 $O(\sum
w
)$，即字典总字符数，每个单词入集合需要哈希一遍；search 为 $O(25 L^2)$，其中 L 是查询词长度——外层 L 个位置、内层 25 个候选字母，每个候选都要构造并哈希一个长度为 L 的字符串。凭什么与字典规模无关：候选集合完全由查询词和字符集决定，字典只承担 $O(L)$ 的哈希查表。
空间复杂度 ：$O(\sum
w
)$。凭什么：哈希集合完整保存了所有字典单词；查询时只额外用一个长度 L 的字符数组和一个候选串，量级更小。
候选枚举的方向要选规模小的那一边 ：与其拿查询词去比对整个字典（规模 $n$），不如生成「差一位」的全部候选（规模 $25L$）再查表。当字典可能很大而字符集很小的时候，这个方向的收益极为可观。
「恰好 K 处不同」这类约束要拆成下界与上界两条 分别落实：本题的下界靠「跳过换成自己」，上界靠「一次只改一位并及时复原」。少任何一条都会得到看起来能过样例、实则错误的实现。
复原是可变缓冲区的纪律 。用可变数组做枚举是为了省内存和时间，代价就是必须自己维护「除当前位外一切照旧」这条不变量，写完枚举循环立刻补上复原语句已经该成为肌肉记忆（回溯法里也是同一条纪律）。
设计类题目要先看调用比例 ：本题 buildDict 只调一次而 search 会调很多次，所以把成本压在预处理上、让查询尽量快是正确的取舍。
面试视角：本题另有一条 Trie + 带修改次数的 DFS 解法——在树上沿查询词下行，额外携带「已用掉几次修改」的参数，允许在某个节点转向别的字符分支但只允许一次，走到词尾时要求修改次数恰好为 1。它在字典极大、需要支持前缀相关扩展时更优。能同时给出两条并说明选择依据（「字符集小、词长短就枚举替换；要支持前缀查询或字典巨大就上 Trie」）是本题的加分答法。
错误写法：内层不跳过 ch == old；用例 buildDict(["hello"]) 后 search("hello") → 候选串包含 hello 自己，命中集合返回 true，正确答案是 false。
错误写法：内层循环结束后忘记把 s[i] 复原；用例 buildDict(["hello"]) 后 search("hallo") → 处理完 i = 0 后首位残留成 z 之类，处理 i = 1 时生成的是「差两位」的串，hello 永远拼不出来，返回 false，正确答案是 true。
错误写法：命中后直接 return true 却把字符数组声明成了成员变量并且不复原；用例 连续两次 search("hhllo") → 第二次查询在被污染的数组上进行，结果不可预测。
错误写法：改用「逐个比对字典单词、统计差异数」但把条件写成 diff <= 1；用例 buildDict(["hello"]) 后 search("hello") → 差异数 0 也被接受，返回 true，正确答案是 false。
错误写法：逐个比对时忘记先判断长度是否相等；用例 buildDict(["hello"]) 后 search("hell") → 逐位比较时下标越界，或按较短长度比较得出「差 0 处」的错误结论。
错误写法：在 buildDict 里就预先生成所有「差一位」的变体存进集合；用例 字典有 100 个长度 100 的单词 → 集合膨胀到 25 万条长串，内存与建表时间都远超必要；更糟的是查询时无法区分「命中的是变体还是原词」，search 传入字典中已有的词会被误判为 true。
错误写法：内层从 'a' 循环到 'z' 时用 int 与 char 混用导致越界，例如 Go 里写 for ch := 'a'; ch <= 'z'; ch++ 得到 rune 再直接赋给 []byte；用例 任意查询 → 类型不匹配编译失败，或强转后写入错误字节。
错误写法：用 List 而不是 Set 存字典并用 contains 查找；用例 字典规模较大且查询频繁 → 每次候选查找退化成 $O(nL)$，总代价变成 $O(25nL^2)$，在更大数据下超时。
错误写法：认为只需比较相同首字母的单词从而按首字母分桶，却忘了差异位可能就在首位；用例 buildDict(["hello"]) 后 search("jello") → 按首字母 j 分桶找不到任何候选，返回 false，正确答案是 true。
错误写法：buildDict 被重复调用时没有清空旧集合（若题目允许多次调用）；用例 先后两次 buildDict → 旧词残留导致查询命中已被替换掉的字典内容。本题只调用一次所以安全，但把状态清理写进构建方法是更稳妥的习惯。
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！