839.相似字符串组

839.相似字符串组

题目

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，”tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的，但是 “star” 不与 “tars”，”rats”，或 “arts” 相似。

总之，它们通过相似性形成了两个关联组：{“tars”, “rats”, “arts”} 和 {“star”}。注意，”tars” 和 “arts” 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

示例 1：

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

示例 2：

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

提示：

1 <= strs.length <= 100
1 <= strs[i].length <= 1000
sum(strs[i].length) <= 2 * 104
strs[i] 只包含小写字母。
strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

备注：

字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

思路

首先贴一下知乎大佬对并查集的详细解读。

只要A和B相似，B和C相似，即使A和C不相似，ABC也是一组。映射到图论中，就是妥妥的求联通集数目的问题，不多BB直接上并查集。

首先解决下如何判断两个字符串相似的问题。很简单，相似的两个字符串，只有两个位置上的字符不一样，其他位置都是一样的，问题解决。
然后解决求联通集数目的问题。所有的字符串两两比较，如果同属于一个联通集（根节点相同），直接不用比了；如果两个字符串不属于同一个联通集且相似，那么合并这两个联通集（一个联通集的根节点认另一个联通集的根节点做爹）。最后统计联通集的总数（统计根节点的数目），问题解决。

解决第一个问题，为了比较两个字符串是否相似，需要O(m)的时间，m是每个字符串的长度；那么两两比较需要O(mn^2)的时间，n是字符串的总数；解决第二个问题，最坏情况下需要对并查集进行O(n)次合并，合并的均摊时间复杂度为O(logn)，logn也就是节点数为n的树的高度（相当于找到根节点的时间）。总的时间复杂度是O(mn^2 + nlogn)。

代码

class Solution {
    private int[] f; // 并查集

    public int numSimilarGroups(String[] strs) {
        /* 初始化并查集 */
        f = new int[strs.length]; 
        for (int i = 0; i < strs.length; ++i) {
            f[i] = i; // 初始时，每个节点的父节点都是自己，单独作为一个联通集
        }

        /* 所有字符串两两比较一遍 */
        for (int i = 0; i < strs.length; ++i) {
            for (int j = i + 1; j < strs.length; ++j) {
                if (find(i) == find(j)) { // 两个节点的根节点一样，说明是同一个联通集的
                    continue;
                } else if (check(strs[i], strs[j], strs[0].length())) { // 两个节点不属于同一个联通集但是经判断后是相似的
                    f[find(i)] = find(j); // 合并两个节点各自所属的联通集，即一个联通集的根节点认另一个联通集的根节点做爹
                }
            }
        }

        /* 查找根节点的数量，即联通集的总数 */
        int num = 0;
        for (int i = 0; i < strs.length; ++i) {
            if (f[i] == i) { // 父节点是自己，即为根节点
                ++num;
            }
        }
        return num;
    }

    // 查找节点的根节点
    private int find(int x) {
        return x == f[x] ? x : (f[x] = find(f[x]));
    }

    // 判断两个字符串是否相似
    private boolean check(String str1, String str2, int length) {
        int count = 0;
        for (int i = 0; i < length; ++i) {
            if (str1.charAt(i) != str2.charAt(i)) {
                ++count;
            }
            if (count > 2) { // 相似的字符串最多只有两个字符不一样
                return false;
            }
        } 
        return true;
    }
}