题目描述
思路解析动画文字版
核心就一个计数：逐位比较，数不同的位数 diff。diff==1 即命中。下面把每一位的比较演给你看。
【查询 "hhllo" · 候选 1/2】格子里是候选词「world」，要和查询词「hhllo」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
指针走到第 0 位。查询词这位是 'h'，候选这位是 'w'，两者不同，diff 要加一。
这位不同，diff 加一变成 1（红色是不同的位）。继续比下一位。
指针走到第 1 位。查询词这位是 'h'，候选这位是 'o'，两者不同，diff 要加一。
这位不同，diff 加一变成 2（红色是不同的位）。继续比下一位。
指针走到第 2 位。查询词这位是 'l'，候选这位是 'r'，两者不同，diff 要加一。
这位不同，diff 加一变成 3（红色是不同的位）。继续比下一位。
指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
这位相同，diff 保持 3（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 4 位。查询词这位是 'o'，候选这位是 'd'，两者不同，diff 要加一。
这位不同，diff 加一变成 4（红色是不同的位）。继续比下一位。
比完整词，一共 4 位不同。diff 不等于 1，改一处变不成「world」，换下一个候选继续试。
【查询 "hhllo" · 候选 2/2】格子里是候选词「hello」，要和查询词「hhllo」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
指针走到第 0 位。查询词这位是 'h'，候选这位是 'h'，两者相同，diff 不变。
这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 1 位。查询词这位是 'h'，候选这位是 'e'，两者不同，diff 要加一。
这位不同，diff 加一变成 1（红色是不同的位）。继续比下一位。
指针走到第 2 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
这位相同，diff 保持 1（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
这位相同，diff 保持 1（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 4 位。查询词这位是 'o'，候选这位是 'o'，两者相同，diff 不变。
这位相同，diff 保持 1（绿色是到目前为止相同的位）。继续比下一位。
比完整词，一共 1 位不同。diff 恰好等于 1，说明只改那一个红色位置就能变成「hello」——命中，search 返回 true。
【查询 "world" · 候选 1/2】格子里是候选词「hello」，要和查询词「world」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
指针走到第 0 位。查询词这位是 'w'，候选这位是 'h'，两者不同，diff 要加一。
这位不同，diff 加一变成 1（红色是不同的位）。继续比下一位。
指针走到第 1 位。查询词这位是 'o'，候选这位是 'e'，两者不同，diff 要加一。
这位不同，diff 加一变成 2（红色是不同的位）。继续比下一位。
指针走到第 2 位。查询词这位是 'r'，候选这位是 'l'，两者不同，diff 要加一。
这位不同，diff 加一变成 3（红色是不同的位）。继续比下一位。
指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
这位相同，diff 保持 3（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 4 位。查询词这位是 'd'，候选这位是 'o'，两者不同，diff 要加一。
这位不同，diff 加一变成 4（红色是不同的位）。继续比下一位。
比完整词，一共 4 位不同。diff 不等于 1，改一处变不成「hello」，换下一个候选继续试。
【查询 "world" · 候选 2/2】格子里是候选词「world」，要和查询词「world」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
指针走到第 0 位。查询词这位是 'w'，候选这位是 'w'，两者相同，diff 不变。
这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 1 位。查询词这位是 'o'，候选这位是 'o'，两者相同，diff 不变。
这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 2 位。查询词这位是 'r'，候选这位是 'r'，两者相同，diff 不变。
这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
指针走到第 4 位。查询词这位是 'd'，候选这位是 'd'，两者相同，diff 不变。
这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
比完整词，一共 0 位不同。diff 不等于 1，改一处变不成「world」，换下一个候选继续试。
查询 "world" 时：和 hello 比 diff=4，和它自己比 diff=0（全绿、一处没改）。没有任何候选的 diff 等于 1，所以恰好改一处变不出新词，返回 false。
三个高频追问：diff 的含义与 diff==1、为什么只比等长、以及 Trie 优化方向。
参考代码
class MagicDictionary: def buildDict(self, words): self.words = words # 存下所有单词 def search(self, word): for w in self.words: if len(w) != len(word): # 只比等长的 continue diff = sum(a != b for a, b in zip(word, w)) if diff == 1: # 恰好改一处 return True return False复杂度
- 时间：O(N·L)，N 是字典单词数，L 是单词长度；每次 search 最多把每个同长单词逐位比一遍
- 空间：O(N·L)，只额外存下字典里的所有单词，比较时不开新数组
易错点
面试追问把动画讲成自己的话
追问diff 是什么，命中条件为什么是 diff==1？
追问为什么只比长度相同的单词？
追问单词非常多时怎么优化？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题