LeetCode 1061. 按字典序排列最小的等效字符串
目录
题目描述
题意分析
给两个等长字符串
s1、s2，规定对每个位置i，字符s1[i]与s2[i]等价。等价关系满足自反、对称、传递三条性质。要求把baseStr中的每个字符替换成与它等价的字符里字典序最小的那个，返回替换后的字符串。题目明确写出「自反、对称、传递」，这是极强的提示：等价关系把 26 个字母切成若干个互不相交的等价类，同一类里的字母可以互相替换。所以真正要回答的问题是：每个字母属于哪一类，以及每一类里最小的字母是谁。
传递性是难点所在。
s1 = "abc"、s2 = "bcd"给出的直接关系只有a~b、b~c、c~d，但a与d也必须被认作等价——关系是可以链式传播的。所以不能只看每一对，必须做合并：不断把有直接关系的两个字母所在的组并成一组。约束里有一条决定性的信息：字符全是小写字母，也就是说参与合并的元素只有 26 个，与字符串长度无关。这让整个「分组」结构的规模变成常数，无论
s1多长，组的数量都不超过 26。1 ≤ s1.length ≤ 1000、1 ≤ baseStr.length ≤ 1000的规模在这个结构下毫无压力。边界：
s1[i]与s2[i]可能相同（自反关系，合并时会发现已在同一组，直接跳过）；同一对关系可能重复出现；baseStr里的字符可能从未在s1、s2中出现过，此时它自成一组，替换结果就是它自己。
解法：并查集合并连通块
核心思路
自反、对称、传递的关系会把 26 个小写字母划分成若干等价类。每一对
s1[i] ~ s2[i]都是在合并两个等价类，最终需要查询每个类中字典序最小的字符，因此并查集正好匹配这两个操作。普通并查集只保证同组元素拥有同一个根，根本身不一定最小。本题把合并规则改为：找到两个集合的根后，始终让编号较小的根成为新根。
不变量：每个集合的根都是该集合中字典序最小的字符。 初始时每个字符自成集合，不变量成立；合并两个集合时，旧根分别是各自集合的最小字符，取二者较小者作为新根，正好仍是合并后集合的最小字符。路径压缩只缩短查找路径，不改变根，因此不会破坏该性质。
所有关系合并完成后，对
baseStr的每个字符执行find，得到的根就是它能替换成的最小等价字符。正确性：并查集对每一对直接关系执行合并，所以直接相连的字符在同一集合；集合合并具有传递性，因此所有通过关系链相连的字符也在同一集合。反过来，只有题目给出的关系会触发合并，不会把无关字符放到一起。结合“根是集合最小字符”的不变量，逐字符替换得到的每一位都已最小，而各位置互不约束，整个结果字符串也就字典序最小。
解题步骤
- 建立长度为 26 的
parent数组，初始化parent[i] = i。- 遍历
s1、s2，对每一对字符先找根，再把较大根挂到较小根下。- 遍历
baseStr，用带路径压缩的find找到每个字符所属集合的最小根，写入答案。例如关系
c ~ d、b ~ c、a ~ b会依次把根从c更新为b、再更新为a。即使d从未与a直接配对，find(d)仍会沿d → c → b → a找到a，并在路径压缩后直接指向a。
s1[i] == s2[i]或重复关系只会让两个根相同，无需额外处理；从未出现在关系中的字符始终以自己为根，替换后保持不变。
代码实现
class Solution {
public String smallestEquivalentString(String s1, String s2, String baseStr) {
int[] parent = new int[26];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < s1.length(); i++) {
int root1 = find(parent, s1.charAt(i) - 'a');
int root2 = find(parent, s2.charAt(i) - 'a');
if (root1 != root2) {
parent[Math.max(root1, root2)] = Math.min(root1, root2);
}
}
StringBuilder answer = new StringBuilder(baseStr.length());
for (int i = 0; i < baseStr.length(); i++) {
int root = find(parent, baseStr.charAt(i) - 'a');
answer.append((char) ('a' + root));
}
return answer.toString();
}
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
parent := make([]int, 26)
for i := range parent {
parent[i] = i
}
var find func(int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
for i := 0; i < len(s1); i++ {
root1 := find(int(s1[i] - 'a'))
root2 := find(int(s2[i] - 'a'))
if root1 < root2 {
parent[root2] = root1
} else if root2 < root1 {
parent[root1] = root2
}
}
answer := make([]byte, len(baseStr))
for i := range baseStr {
root := find(int(baseStr[i] - 'a'))
answer[i] = byte(root) + 'a'
}
return string(answer)
}
复杂度分析
- 时间复杂度：$O(n + m)$，其中
n = s1.length、m = baseStr.length。并查集只有 26 个节点，单次find、合并可视为常数时间。- 空间复杂度：除返回结果外为 $O(1)$，因为
parent固定为 26 个元素；构造长度为m的结果需要 $O(m)$ 空间。
关键点总结
- 等价关系对应连通分量；关系逐条加入、需要传递闭包时优先考虑并查集。
- 让较小根成为新根，把“集合代表”直接维护成“集合最小字符”，查询时无需再扫描集合。
- 合并前必须比较两个根，不能直接修改原字符的父节点。
- 路径压缩不改变集合代表，既保持最小根不变量，也让后续查询更直接。
易错点总结
- 直接比较原字符而不是集合根：先合并
a ~ c，再处理b ~ c时若直接覆盖parent[c] = b，会断开已有的a ~ c关系；正确做法是合并find(b)与find(c)。- 任意选择新根：若固定把第二个根挂到第一个根，
p ~ m可能让p成为代表，无法保证输出组内最小字符。若要按秩合并，就必须额外维护每组最小值；本题只有 26 个节点，直接按字符大小合并更简单。- 构造答案时读取
parent[x]而不是find(x)：关系c ~ d、b ~ c后，parent[d]可能仍是c，但真正的最小根已是b。- 忘记初始化
parent[i] = i：Java 的整型数组默认全为 0，会把所有字母错误地归入a所在集合。- 把关系当成单向替换：题目给的是对称等价关系，不是
s1[i] → s2[i]的映射；单向表无法处理反向和传递替换。- 只初始化关系中出现的字符：
baseStr中未参与任何关系的字符也应自成一组并保持不变，因此 26 个字母必须全部初始化。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 990. 等式方程的可满足性 | 中等 | 同样是 26 个字母的等价类，但要先处理所有等式再用不等式做矛盾检验，顺序不能反 |
| 1202. 交换字符串中的元素 | 中等 | 下标之间连通，同一组内的字符可任意重排，需对每组排序后回填，而非取单个最小值 |
| 547. 省份数量 | 中等 | 只统计连通分量个数，根不携带业务语义，可以放心使用按秩合并 |
| 684. 冗余连接 | 中等 | 利用 union 返回「是否已同组」来定位第一条成环的边，考的是合并的返回值 |
| 721. 账户合并 | 中等 | 元素是邮箱字符串，要先做映射再合并，最后还需按组收集并排序输出 |
| 839. 相似字符串组 | 困难 | 边不是直接给出的，需要两两判断相似性才能建边，合并前的预处理是主要开销 |
| 128. 最长连续序列 | 中等 | 可用并查集维护「组的大小」作为根的业务语义，与本题「根存最小值」是同一套手法 |