LeetCode LCR 117. 相似字符串组

约 7 分钟
文章信息 5 个分类 7 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 字符串 哈希表 深度优先搜索 广度优先搜索 LCR 并查集

题目描述

✅ LCR 117. 相似字符串组

image-20260929004730365

image-20260929004730366

题意分析

两个字符串完全相同，或交换其中一个字符串的两个位置后能相同，就直接相似。若若干字符串能通过直接相似的关系串成一条链，它们属于同一组；同组中的任意两个字符串不必直接相似。题目保证所有字符串等长且互为字母异位词。

解法：逐对比较与并查集分组

核心思路

[!blue]

把每个输入字符串作为一个节点，直接相似的两词之间连边，题目要求的组数就是这个无向图的连通分量数。可以枚举每一对字符串，判断相似时立即用并查集合并，不必真正保存全部图边。

判断相似时统计不同位置数 diff。为 0 时两串相同；为 2 时，由于其余位置相同且两串字符计数完全一致，这两个位置的字符必然交叉对应，交换后即可一致。一次交换最多改变两个位置，所以超过 2 时立即失败。这个判据依赖异位词前提，不能直接用于任意两个字符串。

并查集初始有 n 个独立集合，cnt = n。发现相似对后，先比较两者根：同根说明已经通过其他相似链连通，不再扣减；不同根则合并整组并令 cnt 减一。每次合并都加入一条真实相似关系，所以不会把无关字符串连在一起；枚举完全部字符串对后，也不会遗漏能够间接连通的组。

find 用路径压缩复用已知的集合根，union 用秩控制树形。内容完全相同的输入项也会被正常合并，无需先做字符串去重。相似判断在第三个不同位置提前结束可以减少实际比较，但最坏仍要扫描整串。

解题步骤

  1. 初始化 parent[i] = i、秩数组和组数 cnt = n。
  2. 枚举 i < j 的所有字符串对，每对只比较一次。
  3. 逐位统计不同位置，超过 2 立即判为不相似，最终仅接受 0 或 2。
  4. 相似时查找两者的根，根不同才按秩合并并减少组数。
  5. 返回维护的 cnt，它已经等于最终连通分量数。

代码实现

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^2)$ 对，每对比较最多 $L$ 个字符，并查集合并摊还为 $O(\alpha(n))$。
  • 空间复杂度：$O(n)$，父节点和秩数组各占线性空间，不保存全部相似边；查找递归栈不超过此量级。

关键点总结

[!green]

所有输入互为异位词，因此恰有两处不同就说明这两个位置可交换；不同位置可能超过两处，此时不能一步互换，但仍可能通过其他字符串间接归入同组。并查集保存的是这种传递连通关系。

易错点总结

[!yellow]

  • 完全相同也算相似；在互为异位词的前提下，恰有两处不同可由一次交换得到。
  • 超过两处不同不相似，但不同位置数本身并非只可能为 0 或 2。
  • 分组使用传递连通性，同组中任意两词不必直接相似；合并已同组元素不重复扣减组数。

相似题目

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