LeetCode LCR 117. 相似字符串组
目录
题目描述
题意分析
给一组字符串，它们两两互为字母异位词。定义「相似」为：两个串完全相同，或者恰好在两个位置上字符不同（把这两个位置的字符交换一下就相同了）。相似关系可以传递地把字符串串成一组，问最终能分出多少组。
注意「相似」本身不具有传递性，但「同组」是传递的：题目说的是 A 与 B 相似、B 与 C 相似，则 A、B、C 属于同一组，哪怕 A 与 C 差了四个位置。这句话把问题从「判断关系」变成了「维护等价类」，是整道题的题眼。
约束给得很小：字符串数量不超过 300，单串长度不超过 300。$n^2$ 级别的两两比较只有约 4.5 万对，每对再花 $O(L)$ 比较字符也完全可以接受。约束这么小，等于明说不必去设计什么「按变换枚举邻居」的高级做法——直接枚举所有对是被允许的。
反过来，如果不是所有串互为异位词，「差两个位置」就不足以推出交换后相等；题目保证了异位词这一前提，所以只需数不同位置的个数，不需要再校验交换后是否真的匹配。
边界要盯住：只有一个字符串时答案是 1；全部字符串完全相同时它们两两相似，答案也是 1；没有任何一对相似时答案就是 $n$。这三种情况都应当由主逻辑自然给出，不需要特判。
解法：并查集（Union-Find）
核心思路
最朴素的想法是从某个字符串出发做一次遍历，把能连通到的都标记掉，算作一组，再从下一个未访问的开始。这个想法本身是对的，瓶颈在于每次遍历都要重新计算「谁和谁相似」，而相似判断本身就是 $O(L)$ 的，来回重复计算既麻烦又容易写错。
换个角度看：我们真正需要的不是「路径」，而是「归属」。任意两个串一旦被判定相似，它们就永远属于同一组，此后再也不会分开。这种「只合并、不拆分」的动态等价类，正是并查集的舒适区。
于是把每个字符串抽象成一个编号 $0 \dots n-1$ 的节点，维护数组
parent，其中parent[x]指向 x 的父节点，每棵树的根代表一个组。不变量：任意时刻，
find(i) == find(j)当且仅当在已经处理过的那些字符串对里，i 和 j 之间存在一条相似关系的链。同时计数器cnt恒等于当前不同根的个数。初始时每个节点自成一组，
cnt = n。每当发现一对相似且它们的根不同，就把两棵树接起来并令cnt--；根相同则什么都不做，cnt不变。所有对处理完，cnt就是连通分量数，也就是答案。相似判断本身可以剪枝：一边扫一边数不同位置个数，一旦超过 2 就立即返回 false，不必扫完整个串。最后接受 0 或 2 两种取值——0 是完全相同，2 是恰好交换一对，而由于两串互为异位词，不同位置的个数不可能是 1。
解题步骤
- 建并查集：
parent[i] = i，rank[i] = 0，cnt = n。之所以初值取cnt = n，是因为在没有任何合并前，每个字符串确实各自成组，这个初值让cnt从第一步起就满足不变量。- 枚举所有无序对：外层
i从 0 到 n-1，内层j从i + 1开始。内层从i + 1而不是 0 起，是因为相似关系对称，(i, j)与(j, i)等价，枚举一半省掉一半的比较。- 判定相似：逐位比较，累计
diff，diff > 2时提前返回 false。提前返回不只是常数优化——最坏情况下大量字符串互不相似，早退能把每次比较从 $O(L)$ 压到接近 $O(1)$。- 合并：相似则
union(i, j)。union内部先各自find到根，根相同直接返回（这一步保证cnt不被重复扣减），否则按秩合并并cnt--。- 按秩合并 + 路径压缩：
find递归时顺手把沿途节点直接挂到根上，union时把矮树挂到高树下。两者合起来让单次操作近似 $O(1)$，也避免了退化成链后find变成 $O(n)$。- 返回
cnt：不需要再扫一遍数根，因为cnt一直被维护成正确值。以
strs = ["tars", "rats", "arts", "star"]走一遍。初始parent = [0,1,2,3]，cnt = 4。
(0,1)：tars与rats逐位比较，位置 0 是t对r、位置 2 是r对t，其余相同，diff = 2，相似。find(0)=0、find(1)=1不同，两者秩都是 0，把 1 挂到 0 下并让rank[0]升为 1，cnt = 3。
(0,2)：tars与arts，位置 0 是t对a、位置 1 是a对r、位置 2 是r对t，扫到第三个不同时diff = 3 > 2，提前返回 false，不合并。
(0,3)：tars与star，位置 0 是t对s、位置 1 是a对t、位置 2 是r对a，diff再次超过 2，不相似。
(1,2)：rats与arts，位置 0 是r对a、位置 1 是a对r，其余相同，diff = 2，相似。find(1)走到根 0，find(2) = 2，根不同；rank[0] = 1 > rank[2] = 0，把 2 挂到 0 下，cnt = 2。
(1,3)、(2,3)：rats与star差三位，arts与star差四位，都不相似。全部枚举完毕，
cnt = 2，即{tars, rats, arts}和{star}两组。这里正好体现了传递性的价值：tars与arts并不相似，却因为都与rats相似而被并进同一组。
代码实现
class Solution {
public int numSimilarGroups(String[] strs) {
int n = strs.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isSimilar(strs[i], strs[j])) {
uf.union(i, j);
}
}
}
return uf.count();
}
// 互为异位词时，不同位置个数只可能是 0 或 2；超过 2 立即否定。
private boolean isSimilar(String a, String b) {
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
diff++;
if (diff > 2) {
return false;
}
}
}
return diff == 0 || diff == 2;
}
static class UnionFind {
int[] parent;
int[] rank;
int cnt;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
cnt = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int a, int b) {
int ra = find(a);
int rb = find(b);
// 根已相同说明早已同组，不能再扣减计数。
if (ra == rb) {
return;
}
if (rank[ra] < rank[rb]) {
parent[ra] = rb;
} else if (rank[ra] > rank[rb]) {
parent[rb] = ra;
} else {
parent[rb] = ra;
rank[ra]++;
}
cnt--;
}
int count() {
return cnt;
}
}
}
func numSimilarGroups(strs []string) int {
n := len(strs)
uf := newUF(n)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if isSimilar(strs[i], strs[j]) {
uf.union(i, j)
}
}
}
return uf.cnt
}
// 互为异位词时，不同位置个数只可能是 0 或 2；超过 2 立即否定。
func isSimilar(a, b string) bool {
diff := 0
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
diff++
if diff > 2 {
return false
}
}
}
return diff == 0 || diff == 2
}
type uf struct {
parent []int
rank []int
cnt int
}
func newUF(n int) *uf {
p := make([]int, n)
r := make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
}
return &uf{parent: p, rank: r, cnt: n}
}
func (u *uf) find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.find(u.parent[x])
}
return u.parent[x]
}
func (u *uf) union(a, b int) {
ra := u.find(a)
rb := u.find(b)
// 根已相同说明早已同组，不能再扣减计数。
if ra == rb {
return
}
if u.rank[ra] < u.rank[rb] {
u.parent[ra] = rb
} else if u.rank[ra] > u.rank[rb] {
u.parent[rb] = ra
} else {
u.parent[rb] = ra
u.rank[ra]++
}
u.cnt--
}
复杂度分析
- 时间复杂度：$O(n^2 L)$。枚举 $\frac{n(n-1)}{2}$ 对，每对的相似判断最坏扫完整串是 $O(L)$；并查集操作在路径压缩加按秩合并下摊还近似常数，被 $O(L)$ 淹没。
- 空间复杂度：$O(n)$。只有
parent与rank两个长度为 $n$ 的数组，相似判断原地比较不额外开串；find的递归深度因路径压缩与按秩合并被控制在 $O(\log n)$ 以内。
关键点总结
- 看到「关系可传递地分组」「问有多少组」，先想连通分量；如果关系只增不减，并查集通常比建图再遍历更省事。
- 并查集的组数不要最后扫一遍数根，而是在
union成功时递减计数器——这样计数逻辑与合并逻辑绑定在一起，天然不会重复扣减。- 「相似」不传递而「同组」传递，是这类题最容易被误读的地方；面试时主动点破这一点，能立刻证明你读懂了题。
- 约束规模是解法的路标：$n \le 300$ 明说了 $O(n^2)$ 可行，不必为更优复杂度做无谓设计。面试中先说「约束允许我枚举所有对」，比直接甩解法更有说服力。
- 判定函数里加提前返回，是把最坏复杂度和平均复杂度拉开的廉价手段，写起来只多两行。
- 路径压缩与按秩合并要一起讲：只有压缩没有按秩也能过，但被追问时能说清两者各自解决什么问题，才是完整回答。
易错点总结
- 内层循环从 0 开始：
["tars","rats"]会把(0,1)和(1,0)各判一次，虽然union内部有根相同的保护不至于答案出错，但白白多花一倍时间；更糟的是若把cnt--写在find之外，答案会直接少算。union里不判根是否相同就cnt--：["ab","ab","ab"]（假设长度合法）中三对全部相似，cnt会从 3 减到 0，返回 0 而正确答案是 1。- 相似判定漏掉
diff == 0：["aa","aa"]两串完全相同，diff = 0，若只接受diff == 2会判为不相似，返回 2 而正确答案是 1。- 相似判定写成
diff <= 2：由于互为异位词，diff = 1不可能出现，写<= 2在本题不会出错，但换成不保证异位词的变体就会把「只差一位」误判为相似，是逻辑上的隐患。- 提前返回的阈值写成
diff >= 2：["tars","rats"]扫到第二个不同位置就返回 false，正确答案 1 会被算成 2。必须是严格大于 2 才能否定。find忘记路径压缩且用朴素合并：构造一条长链（如 300 个首尾相似的串顺次合并成链），find退化成 $O(n)$，总复杂度升到 $O(n^3)$，在极端数据上超时。union里对parent直接赋值而不先find：写成parent[a] = b而非parent[find(a)] = find(b)，会把已经挂在别的根下的节点强行改父，破坏树结构，["tars","rats","arts"]可能算出 2 组。- 按秩合并时忘记只在秩相等才
rank++：把两个不同秩的树合并后也自增，秩失去「树高上界」的语义，退化保护失效，深链场景下性能回落。- Go 版用值接收者定义
find：func (u uf) find(...)会拷贝结构体，路径压缩写进副本、对外不生效，功能上仍能算对答案但性能退化；必须用指针接收者。- 误以为要返回最大组的大小：题目问的是组数不是组的规模，返回
max(size)在["tars","rats","arts","star"]上会给出 3 而不是 2。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 547. 省份数量 | 中等 | 邻接矩阵直接给出边，省掉本题的相似判定，是本题的裸模板版 |
| 323. 无向图中连通分量的数目 | 中等 | 边以列表形式给出，只需遍历边表合并，无需 $O(n^2)$ 枚举点对 |
| 684. 冗余连接 | 中等 | 关注的是 union 失败的那一刻（根已相同即成环），而非最终组数 |
| 721. 账户合并 | 中等 | 需先用哈希表把邮箱映射成编号再并查集，合并后还要按根归集并排序 |
| 990. 等式方程的可满足性 | 中等 | 分两轮处理：先合并所有等式，再逐条检查不等式是否与已合并结果冲突 |
| 1202. 交换字符串中的元素 | 中等 | 合并出下标的连通块后，还要在每块内部对字符排序以求字典序最小 |
| 765. 情侣牵手 | 困难 | 答案是「节点数减连通分量数」，考的是最少交换次数与分量数的换算 |
| LCR 116. 省份数量 | 中等 | 与 547 同题 |
| LCR 118. 冗余连接 | 中等 | 与 684 同题 |
| 面试题 17.07. 婴儿名字 | 中等 | 合并时要额外维护「字典序最小的名字」作为组代表，并累加频次 |