题目描述
思路解析动画文字版
记住这个约定:合并两类时,大字母指向小字母,小的当根。下面每一帧都在套它。
初始 · 5 个字母各自独立：先把例子里出现的 5 个字母 a、b、c、d、e 摆出来。一开始谁也不连谁,每个字母自己是一类,所以等价类个数是 5。接下来按 s1、s2 一列一列地合并。
三列等价关系 · 待合并：s1 和 s2 对齐看:第 0 列 a 配 c、第 1 列 b 配 d、第 2 列 c 配 e。也就是要把 a 和 c、b 和 d、c 和 e 分别连起来。一列一列处理。
第 0 列 · a 等价 c：看第 0 列:s1 的 a 和 s2 的 c 等价。先紫色点亮这两个字母,准备把它们并到一类。
找代表元 · a→a, c→c：合并前先各自找代表元(也就是树根)。现在 a 的根是 a、c 的根是 c,两个都还是自己,谁也没被合并过。
合并 · c 指向 a：a 比 c 小,按约定小的当根,所以让 c 指向 a。现在 a 和 c 同一类、根是 a。等价类个数从 5 降到 4。
第 1 列 · b 等价 d：看第 1 列:s1 的 b 和 s2 的 d 等价。点亮 b 和 d,准备合并。
找代表元 · b→b, d→d：b 的根是 b、d 的根是 d,都还独立。它们和左边那组没关系,是另一棵树。
合并 · d 指向 b：b 比 d 小,让 d 指向 b,根是 b。现在有两组:{a,c} 和 {b,d}。等价类个数降到 3。
第 2 列 · c 等价 e：看第 2 列:s1 的 c 和 s2 的 e 等价。注意 c 之前已经和 a 一类了,这一步会把 e 也拉进来,传递性就体现在这。
找代表元 · c→a, e→e：关键一步:找 c 的根,c 指向 a,所以 c 的根是 a,不是 c。e 还是自己。所以真正要合并的是代表 a 和代表 e,而不是 c 和 e。
合并 · e 指向 a：a 比 e 小,让 e 指向 a。现在 e、c 都挂在 a 下面,a 这一类成了 {a,c,e}。等价类个数降到 2。
传递成型 · {a,c,e} 同根 a：回看这棵树:c 指 a、e 指 a,a 自己是根。a 是 {a,c,e} 里字典序最小的,正因为每次合并都让小字母当根,根天然就是这一类的最小值。
两组定型 · 映射就绪：三列处理完,字母分成两类:{a,c,e} 都映射到 a,{b,d} 都映射到 b。这张映射表就是替换 baseStr 的依据。
替换 baseStr · "eed"：并查集建好了,现在处理 baseStr="eed"。逐个字母查它的根,把根写下来,拼成答案。
查 baseStr[0] = e：第 0 个字母是 e。去并查集里查 e 的根:e 指向 a,a 是根。
e → a · 写下 a：e 的根是 a,所以第 0 位写 a。目前答案是 "a"。
查 baseStr[1] = e：第 1 个字母还是 e,根同样是 a,不用重新推。
e → a · 写下 a：第 1 位也写 a。答案变成 "aa"。
查 baseStr[2] = d：第 2 个字母是 d。查 d 的根:d 指向 b,b 是根。它属于另一组 {b,d}。
d → b · 写下 b：d 的根是 b,所以第 2 位写 b。答案现在是 "aab"。
完成 · 答案 "aab"：三个字母都替换完:e→a、e→a、d→b,baseStr "eed" 变成 "aab"。因为每一类的根都是它的最小字母,这样换出来的串字典序一定最小。
边界先想清:无等价信息就原样返回,有信息就全部归到最小字母。
两个高频追问:可用图连通分量替代;按秩合并与「取小根」冲突,这里只压缩、不按秩。
参考代码
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 TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(26)) for a, b in zip(s1, s2): x, y = ord(a) - ord("a"), ord(b) - ord("a") px, py = find(x), find(y) if px < py: p[py] = px else: p[px] = py return "".join(chr(find(ord(c) - ord("a")) + ord("a")) for c in baseStr)复杂度
- 时间：O((n+m)·α)，n 是 s1 长度做 n 次合并、m 是 baseStr 长度做 m 次查询,α 是并查集近似常数的反阿克曼
- 空间：O(1)，parent 数组固定 26 个字母,与输入规模无关
易错点
面试追问把动画讲成自己的话
追问能不能不用并查集,用别的方法?
追问需要路径压缩或按秩合并吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二进制矩阵中的最短路径
LeetCode 1091 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题