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