解题思路与代码实现

题目分析

这道题目要求我们找到字符串列表 strs 中的相似字符组。两字符串相似是指，它们通过交换某些字符可以互相转化。在问题中，如果两个字符串相互相似，那么它们可以归为同一组。我们需要找出字符串列表中有多少个相似字符组。

• 字符组的定义：通过交换某些位置的字符来形成的字符串。
• 相似性判断：如果字符串通过交换最多两个字符的位置，可以互相转换，则它们属于同一组。

这是一个图论中的联通分量问题，可以通过并查集（Union-Find）或者深度优先搜索（DFS）来求解。

---

一、解题策略

本题可以通过并查集来解决。并查集是一种适合解决连通性问题的数据结构，特别适合用于合并集合和查询集合是否连通的操作。对于每个字符串，我们都需要遍历并检查它是否和列表中其他字符串相似，如果相似，就将它们合并到一个组。

1. 初始化并查集：对于每一个字符串，将其看作是一个节点，初始化并查集。
2. 相似性判断：对于任意两个字符串，如果它们相似，则将它们合并到同一集合。
3. 计数连通分量：最后统计并查集中有多少个连通分量，即有多少个相似字符组。

关键步骤：

1. 相似判断函数：用来判断两个字符串是否相似（最多两个字符不同）。
2. 并查集的合并与查找操作。

---

二、代码实现

class Solution {
    // 并查集数组
    int[] parent;

    // 查找操作
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并操作
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 合并两个集合
        }
    }

    // 判断两个字符串是否相似
    public 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) {  // 如果超过2个位置不同，则不相似
                    return false;
                }
            }
        }
        return true;
    }

    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        parent = 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(i, j);
                }
            }
        }

        // 统计连通分量的数量
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (find(i) == i) {  // 如果是根节点，则表示是一个新的字符组
                count++;
            }
        }

        return count;
    }
}

---

三、代码解析

1. 并查集初始化：parent[i] = i，表示每个节点一开始都是独立的组，自己是自己的父节点。
2. 相似性判断：通过遍历字符串的每个字符，统计不同字符的个数，如果超过2个字符不相同，则它们不相似。
3. 合并集合：通过 union(i, j) 来合并两个相似的字符串。
4. 查找连通分量：最终通过查找根节点，统计有多少个独立的组（即多少个相似字符组）。

---

四、复杂度分析

• 时间复杂度：

  • 并查集的初始化为 O(n)，其中 n 是字符串的数量。
  • 双重循环判断字符串的相似性，复杂度为 O(n^2 * m)，其中 m 是字符串的长度，因为每次比较字符串相似性需要 O(m) 的时间。
  • 合并和查找的操作接近常数时间，路径压缩可以使得查找的时间复杂度接近于 O(1)。
  • 总的时间复杂度为 O(n^2 * m)。

• 空间复杂度：

  • 主要空间开销是并查集的数组 parent，占用 O(n) 的空间。
  • 额外的空间开销较少，因此总的空间复杂度为 O(n)。

---

五、运行示例

示例1：

输入：strs = ["tars","rats","arts","star"]
输出：2

 

解释：

• "tars" 和 "rats" 相似（交换1次）。
• "rats" 和 "arts" 相似（交换1次）。
• "arts" 和 "star" 相似（交换1次）。 所以这四个字符串形成一个相似字符组，答案是 1。

示例2：

输入：strs = ["omv","ovm"]
输出：1

 

解释：

• "omv" 和 "ovm" 相似（交换1次）。 所以它们属于同一组，答案是 1。

---

六、总结

在这道题中，我们通过并查集结构实现了对相似字符组的判断和合并操作。通过设计相似性判断函数，我们能够准确地将相似的字符串分为一组。最终，通过并查集的查找操作，统计出有多少个相似字符组。通过这种方法，我们解决了字符串相似性分组的问题，并且该算法具有较好的时间和空间效率。