以下是 LeetCode 839 题“相似字符串组”的 Java 解法，使用并查集将相似的字符串合并，最后统计连通分量个数。

class Solution {
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        // 枚举所有字符串对，如果相似则合并
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    union(parent, rank, i, j);
                }
            }
        }

        // 统计根节点个数（即组数）
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == i) {
                count++;
            }
        }
        return count;
    }

    // 判断两个字符串是否相似
    private boolean isSimilar(String s1, String s2) {
        if (s1.equals(s2)) return true;
        int len = s1.length();
        // 记录不同字符的位置，最多允许两处不同
        int first = -1, second = -1;
        int diff = 0;
        for (int i = 0; i < len; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
                if (diff == 1) first = i;
                else if (diff == 2) second = i;
                else return false; // 超过两处不同，肯定不相似
            }
        }
        // diff == 0 已在开头处理，此处 diff 只可能为 2
        return diff == 2 
            && s1.charAt(first) == s2.charAt(second) 
            && s1.charAt(second) == s2.charAt(first);
    }

    // 并查集：查找（路径压缩）
    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    // 并查集：合并（按秩优化）
    private void union(int[] parent, int[] rank, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

解题思路

1. 相似性定义
   两个字符串相似当且仅当它们相等，或者恰好有两个位置不同且交换这两个位置的字符后相等。
2. 并查集分组
   · 初始化每个字符串的父节点为自己。
   · 遍历所有字符串对 (i, j)，如果 strs[i] 与 strs[j] 相似，则在并查集中合并它们。
   · 最后统计根节点的个数，即为组的数量。
3. 相似性判断优化
   · 先检查是否相等。
   · 遍历一次，记录不同字符的位置，一旦超过两处立即返回 false。
   · 若恰好两处不同，检查是否可通过交换使两字符串相等。

复杂度分析

· 时间复杂度：O(n²·L)，其中 n 是字符串个数，L 是字符串长度。双重循环加每次相似性判断的 O(L) 扫描。
· 空间复杂度：O(n)，用于并查集数组。

该解法适用于 LeetCode 原题的数据范围（通常 n ≤ 100，L ≤ 1000），能够正确通过。