题目描述
思路解析
一句话答案：LeetCode 890 查找和替换模式：判断每个单词能否靠一套字母双射变成模式串 pattern，用词→式、式→词两张映射表逐位比对，双向都不撞车才算匹配，时间 O(n·L)、空间 O(1)。
哪些单词换套字母表就能拼成 pattern
给一串单词 words 和模式串 pattern，挑出所有能匹配 pattern 的单词。匹配叫双射：存在一套字母替换，不同字母换成不同字母、不撞到一起，把 pattern 替换后正好得到那个单词。题面例子 words=["abc","mee","aqq","ccc"]、pattern="abb"，答案是 ["mee","aqq"]。abb 的形状是「头一位单、后两位相同」，只有 mee、aqq 对得上。
只记「词→式」一张表，为什么会放错人
先试只开一张映射表：逐位记「词字母 → 式字母」，同一个词字母始终指向同一个式字母就算过。这只拦得住『一个词字母对应两个式字母』一种冲突。abc 对 abb 时，词 a→式 a、b→式 b、c→式 b，三个词字母互不相同，表里全程没矛盾，abc 就被误放行。可 abc 的 b、c 明明不同，单向表却看不出「b、c 挤到了同一个式字母 b」。
补一张反向表，双向一致才配叫双射
补第二张表，反过来记「式字母 → 词字母」。逐位查时两张表都问：词字母、式字母只要之前登记过，就都得仍指向原先配对的那个。回到 abc 第三位，词 c 在正向表是新面孔，但反向表里式 b 早被词 b 占住、又要它对应 c，反向表当场拦下。
两表各管一个方向，缺一不可：正向表挡『一个词字母想对两个式字母』，ccc 栽在这（词 c 先配 a 又想配 b）；反向表挡『两个词字母挤向同一个式字母』，abc 栽的正是这类。只守一边，总有一类撞车溜过去。
一位一位地查，一撞车就立刻收手
每个单词都从两张空表起步，和 pattern 逐位往下走。每到一位两张表各验一遍：对得上就把「词字母 ↔ 式字母」双向登记，再看下一位；任一张表冲突就立刻出局，后面不再看，前面矛盾了后面再对也救不回。走完两表始终一致就收进答案。
拿 abc、mee、aqq、ccc 逐位对 abb
abc 对 abb：第 0 位 a 配 a、第 1 位 b 配 b 都是新对，双向记下；第 2 位 c 要配 b，反向表里式 b 已归词 b，撞车出局。mee 对 abb：m 配 a、e 配 b 是新对，第 2 位又 e 配 b，两表都已登记且吻合，三位过，进答案。
aqq 也顺：q 配 b 后第 2 位又一次 q 配 b 正好对上，收进答案。ccc 卡在第 1 位：第 0 位 c 配 a，第 1 位 c 又要配 b，正向表里 c 已指向 a，冲突出局。能匹配 abb 的是 mee、aqq，正是题面给的 ["mee","aqq"]。
扫一遍要多久，单字母和全同字符怎么算
设有 n 个单词、每个长 L，逐位扫一遍两张定长小表，总时间 O(n·L)；映射只落在 26 个小写字母上，两张表大小固定，空间 O(1)。pattern 若只有一个字母，任何等长单词都天然匹配；单词形状和 pattern 对不上则一个都进不了答案，比如 abb 要后两位相同、abc 不同当场排除。
参考代码没真开两张字典，而是给每个字母记下最近出现的位置，逐位要求词字母与式字母的最近位置相等，相等即说明它俩一路成对现身，和两张映射表等价。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「一位一查、双向一致才放行」，下面每一帧都在套它。
先看清模式 "abb"：它的形状是「第一位单独，后两位相同」。任何匹配它的词，也必须是这个形状。逐个单词检验。
换到单词 "abc"。两张映射表清空，准备一位一位地和模式 "abb" 对。
第 0 位是新字母对:把「词 a → 式 a」记进 f，反过来「式 a → 词 a」记进 g。这一位绿了。
第 1 位是新字母对:把「词 b → 式 b」记进 f，反过来「式 b → 词 b」记进 g。这一位绿了。
第 2 位想把词 "c" 和式 "b" 配起来，可映射表里 式字母 "b" 早先已被词字母 "b" 占用，这一位却要它对应 "c"。撞车了，这个词出局。
"abc" 在第 2 位就撞了车，没法构成双射。丢弃，不进答案。
换到单词 "mee"。两张映射表清空，准备一位一位地和模式 "abb" 对。
第 0 位是新字母对:把「词 m → 式 a」记进 f，反过来「式 a → 词 m」记进 g。这一位绿了。
第 1 位是新字母对:把「词 e → 式 b」记进 f，反过来「式 b → 词 e」记进 g。这一位绿了。
第 2 位的词 "e" 和式 "b" 在两张表里都已登记且正好对得上，一致通过，绿色推进到第 2 位。
"mee" 从头到尾两张表都没冲突，说明能用一个双射把模式变成它。收进答案。
换到单词 "aqq"。两张映射表清空，准备一位一位地和模式 "abb" 对。
第 0 位是新字母对:把「词 a → 式 a」记进 f，反过来「式 a → 词 a」记进 g。这一位绿了。
第 1 位是新字母对:把「词 q → 式 b」记进 f，反过来「式 b → 词 q」记进 g。这一位绿了。
第 2 位的词 "q" 和式 "b" 在两张表里都已登记且正好对得上，一致通过，绿色推进到第 2 位。
"aqq" 从头到尾两张表都没冲突，说明能用一个双射把模式变成它。收进答案。
换到单词 "ccc"。两张映射表清空，准备一位一位地和模式 "abb" 对。
第 0 位是新字母对:把「词 c → 式 a」记进 f，反过来「式 a → 词 c」记进 g。这一位绿了。
第 1 位想把词 "c" 和式 "b" 配起来，可映射表里 词字母 "c" 早先已对应式字母 "a"，这一位却要它对应 "b"。撞车了，这个词出局。
"ccc" 在第 1 位就撞了车，没法构成双射。丢弃，不进答案。
四个单词都对完了,能匹配模式 "abb" 的是 "mee" 和 "aqq"。这就是最终答案。
边界先想清:单字母全过、形状不合就空、全同对全同能成。
两个高频追问，核心都在「如何稳妥地判两个串是否同构」。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: def match(s, t): m1, m2 = [0] * 128, [0] * 128 for i, (a, b) in enumerate(zip(s, t), 1): if m1[ord(a)] != m2[ord(b)]: return False m1[ord(a)] = m2[ord(b)] = i return True return [word for word in words if match(word, pattern)]复杂度
- 时间：O(n · L)，n 个单词，每个长 L，逐位扫一遍
- 空间：O(1)，映射只在小写字母上，至多 26 项，视为常数
易错点
面试追问把动画讲成自己的话
追问能不能只用一张映射表？
追问有没有不建两张表的等价写法？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
漂亮数组
LeetCode 932 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题