LeetCode 839. 相似字符串组

约 7 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 字符串 哈希表 深度优先搜索 广度优先搜索 并查集

题目描述

✅ 839. 相似字符串组

image-20260929104930588

image-20260929104930737

题意分析

所有字符串等长且两两互为字母异位词。两个字符串完全相同，或交换其中两个位置后能够相同，就称为直接相似。只要能通过一串直接相似关系连接，就属于同一组，要求返回组数，而不是相似对数或最大组大小。

解法：并查集（Union-Find）

核心思路

[!blue]

将每个字符串看作一个节点，直接相似的两个字符串之间连边。题目要求的组就是这张无向图的连通分量：同组内的两个字符串不必直接相似，只需存在相似路径。因此枚举所有字符串对，发现相似时用并查集合并即可，不必保存整张图。

判定相似时，只需统计不同位置的数量。为 0 时两串相同；超过 2 时，一次交换最多改变两个位置，不可能完成转换。恰为 2 时，由于两串互为异位词，去掉其他相同位置后，剩余两对字符的总数也必须相同，而对应位置又都不相等，所以两处字符必然交叉对应，交换后就能相同。

这个“两处不同就相似”的结论依赖异位词前提，不能直接用于任意两个字符串。代码同时检查差异数为 0 或 2，并在超过 2 时提前返回，避免继续扫描已经不可能相似的字符对。

初始每个字符串独立成组，cnt = n。合并时先找两者的根：根相同说明此前的相似路径已把它们连通，不能再次减少组数；根不同才合并并令 cnt--。所有直接相似边都处理后，任意相似路径上的节点都已同组，而没有路径的节点从未被合并，因此剩余组数就是答案。

并查集用路径压缩缩短后续查找，再按秩把较浅的树挂到较深的树上，避免频繁合并形成长链。重复字符串的差异数为 0，也会正常合并到同组。

解题步骤

  1. 每个字符串先独立成组。
  2. 枚举所有不重复的字符串对，统计不同位置。
  3. 相似则合并其并查集根。
  4. 返回成功合并后剩余的组数。

代码实现

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();
    }

    // 互为异位词时，不同位置为零或二才相似，超过二即可排除。
    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
}

// 互为异位词时，不同位置为零或二才相似，超过二即可排除。
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+\alpha(n)))$ 上界，n 为字符串数、L 为单串长度。
  • 空间复杂度：$O(n)$，父节点和秩数组。

关键点总结

[!green]

  • 相似关系不必传递，同组关系由连通性定义。
  • 异位词前提让不同位置计数足以判定一次交换。
  • 组数只在两个不同集合合并时减一。

易错点总结

[!yellow]

  • 忽略完全相同的字符串：重复字符串应属于同组。
  • 发现第二个不同位置就否定：恰好二处仍然相似。
  • 每条相似边都减少组数：同组内的边会重复扣减。
  • 把组数换成最大组大小：回答的不是题目所问。

相似题目

题目 难度 关联与区别
1202. 交换字符串中的元素 中等 同样把可交换关系转成连通分量，原题分量内重排字符，本题把相似字符串连边后计组数。
721. 账户合并 中等 同样通过局部关联求传递闭包分组，原题共享邮箱，本题满足一次交换的字符串相似关系。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/56387538
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！