LeetCode 839. 相似字符串组

2022-10-07 HGNULB 约 12 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 839. 相似字符串组

题意分析

给一组字符串，它们两两互为字母异位词。定义「相似」为：两个串完全相同，或者恰好在两个位置上字符不同（把这两个位置的字符交换一下就相同了）。相似关系可以传递地把字符串串成一组，问最终能分出多少组。

注意「相似」本身不具有传递性，但「同组」是传递的：题目说的是 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 117. 相似字符串组	困难	与本题同题，可直接套用
LCR 116. 省份数量	中等	与 547 同题
LCR 118. 冗余连接	中等	与 684 同题
面试题 17.07. 婴儿名字	中等	合并时要额外维护「字典序最小的名字」作为组代表，并累加频次