1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class UF {
public:
vector<int> f;
vector<int> size;
int n;
int setCount;
UF(int _n): n(_n), setCount(_n), f(_n), size(_n, 1) {
iota(f.begin(), f.end(), 0);
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
bool _union(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return false;
if (size[x] < size[y])
swap(x, y);
f[y] = x;
size[x] += size[y];
--setCount;
return true;
}
bool connected(int x, int y) {
return find(x) == find(y);
}
};
class Solution {
public:
bool check(const string &a, const string &b, int len) {
int num = 0;
for (int i = 0; i < len; i++)
if (a[i] != b[i])
if (++num > 2) return false;
return true;
}
int numSimilarGroups(vector<string> &strs) {
const int n = strs.size(), m = strs[0].length();
UF uf(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
if (uf.connected(i, j)) continue;
if (check(strs[i], strs[j], m))
uf._union(i, j);
}
return uf.setCount;
}
};
|