LeetCode 1202. 【并查集】交换字符串中的元素
原题链接
简单
作者:
大明湖的鱼
,
2021-01-11 18:22:24
,
所有人可见
,
阅读 323
注释说了个问题
class Solution {
public:
int father[100010];
int find(int x){
return x == father[x] ? x : (father[x] = find(father[x])) ;
}
void merge(int x ,int y){
father[find(x)] = find(y) ;
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int cnt[100010] = {0};
string areastr[100010];
int n = s.size();
for(int i = 0 ;i < n ;i ++){
father[i] = i;
}
for(auto it : pairs){
merge(it[1],it[0]);
}
for(int i = 0 ;i < n ; i++){
areastr[find(i)] += s[i]; //这里find[i]为什么不能换成father[i]?
}
for(int i = 0 ;i < n ;i ++){ //这里是不是重复排序了
sort(areastr[i].begin(),areastr[i].end());
}
for(int i =0 ;i<n;i++){
s[i] = areastr[father[i]][cnt[father[i]]++];
}
return s;
}
};