题目描述
思路解析动画文字版
记住这套「一位一查、双向一致才放行」，下面每一帧都在套它。
先看清模式 "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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题