839. Similar String Groups

问题：

给定一组字符串，若其中两个字符串中，其中一个字符串任意两个字符互换后=另一个字符串，那么说这两个字符串相似。

求这组字符串中的相似字符串组，有多少个。

Example 1:
Input: A = ["tars","rats","arts","star"]
Output: 2

Constraints:
1 <= A.length <= 2000
1 <= A[i].length <= 1000
A.length * A[i].length <= 20000
All words in A consist of lowercase letters only.
All words in A have the same length and are anagrams of each other.
The judging time limit has been increased for this question.

解法：并查集（Disjoint Set）

将index作为对象，在DisjointSet中进行操作。

相似的算法：

1     bool isSimilar(string& a, string& b) {
2         int n=0;
3         for(int i=0; i<a.length(); i++) {
4             if(a[i]!=b[i] && ++n>2) return false;
5         }
6         return true;
7     }

其中不相同的字符超过2个，则不相似。

代码参考：

 1 class Solution {
 2 public:
 3     bool isSimilar(string& a, string& b) {
 4         int n=0;
 5         for(int i=0; i<a.length(); i++) {
 6             if(a[i]!=b[i] && ++n>2) return false;
 7         }
 8         return true;
 9     }
10     int numSimilarGroups(vector<string>& A) {
11         DisjointSet DS(A.size());
12         for(int i=1; i<A.size(); i++) {
13             for(int j=0; j<i; j++) {
14                 if(isSimilar(A[i], A[j])) {
15                     DS.merge(i, j);
16                 }
17             }
18         }
19         return DS.getGroupCount();
20     }
21 };

Disjoint Set类的代码参考：

 1 class DisjointSet {
 2 public:
 3     DisjointSet(int n):root(n, 0), rank(n, 0) {
 4         for(int i=0; i<n; i++) {
 5             root[i] = i;
 6         }
 7     }
 8     int find(int i) {
 9         if(i != root[i]) {
10             root[i] = find(root[i]);
11         }
12         return root[i];
13     }
14     bool merge(int x, int y) {
15         int x_root = find(x);
16         int y_root = find(y);
17         if(x_root == y_root) return false;
18         if(rank[x_root] > rank[y_root]) {
19             root[y_root] = x_root;
20         } else if(rank[y_root] > rank[x_root]) {
21             root[x_root] = y_root;
22         } else {
23             root[x_root] = y_root;
24             rank[y_root]++;
25         }
26         return true;
27     }
28     int getGroupCount() {
29         int res = 0;
30         for(int i=0; i<root.size(); i++) {
31             if(root[i] == i) res++;
32         }
33         return res;
34     }
35 private:
36     vector<int> root;
37     vector<int> rank;
38 };