【好像解释的通了,逻辑是正确的】
根据助教的题解来注释。若有大佬发现错误,请指出。 Union是合并的意思。
算法:$O(n^2m)$ ①遍历②并查集合并
- 遍历判断相似
- 并查集合并相似的
- 结果就是并查集中的《所有父亲是其自身》集合个数
我想助教的uni(x, y){...}函数功能等价于
f[find(x)] = find(y)
def union(a,b):
a,b=find(a),find(b)
if a==b: return False
if size[a]<size[b]:
a,b=b,a
parent[b]=a # parent即这里的f 并查集
size[a]+=size[b]
nonlocal nSet
nSet-=1
return True
$\color{cyan}{对的,uni改成这句以后一样AC了}$
class Solution {
public:
vector<int> f, sz; //数列 f 并查集, sz[i] 即第i项的大小
int find(int x){
return x == f[x] ? x : x = find(f[x]); //并查集函数,find里存父father节点.
//注; ?为cpp条件运算法,判断结果为真时取左边的(x), 否时取右边(x = find(f[x]))
}
void uni(int x, int y){ //合并x, y项,sz即size(), 这第i项的集合里的大小
if (sz[x] > sz[y]){ //如果x比y大,第y项指为x,第x项大小 + y
f[y] = x;
sz[x] += sz[y];
}
else{
f[x] = y;
sz[y] += sz[x]; //反之亦然。vice versa.
}
}
bool check(int i, int j, const vector<string>& A){
int total = 0, l_1 = -1, l_2 = -1; //l_1, l_2两个指针来找数
int m = A[i].size(); //字符串长度
for (int k = 0; k < m; k++) //遍历字符串(A里的i,j项) ,注:即input输入的数据
if (A[i][k] != A[j][k]){
total ++; //如果i,j字符串的第k位不一样,total加一
if(total == 1) //于是第一个不同的位置(index),第一个指针就是k(①第k位)
l_1 = k;
else if (total == 2) //第二个不同的位置
l_2 = k;
else return false;
}
if (total == 0) return true; //如果空或者说每一位都相同,即重复字符串。(好像不存在这种情况,那应该就是对空数据的特判) 返回成立
if (total == 1) return false; //只有一处不同而第二处没找到,不符合题意 false
if (A[i][l_1] == A[j][l_2] && A[i][l_2] == A[j][l_1]) return true;
//如果第一个数A[i]里第一个指针位等于第二个数A[j]里第二指针位,反之亦然的话,就说他们是相似的 (题意)
return false;
}
int numSimilarGroups(vector<string>& A) {
int n = A.size(), m= A[0].size(); // n 一个几个词,m即这个词的长度 (他们几个都是一个长度的)
f.resize(n);
sz.resize(n); //数组大小修正,上一行同理
for (int i = 0; i < n; i++){
f[i] = i; //初始化并查集
sz[i] = 1;
}
// f : [0, 1, ..., n - 1]
// sz: [1, 1, ..., 1]
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++){
int x = find(i), y = find(j); //遍历到的当前这两个数,咱们叫他x, y.
if (x == y) continue; //这行需要大佬补充解释一下
if (check(i, j, A)) uni(x, y); //如果这两相似,合并他们
}
int ans = 0;
for (int i = 0; i < n; i++)
if (i == find(i)) ans ++; //并查集里找父节点等于自身的集合的数量
return ans;
}
};