1202 交换字符串中的元素
题目:
给你一个字符串s
,以及pairs[ [a,b], [c, d]]
其中pairs[i] = [a, b]
表示s[a]
和 s[b]
可以相互交换
求经过若干次的交换后,字典序最小的字符串s
输入:s = "dcab", pairs = [[0,3],[1,2]]
输出:"bacd"
解释:交换 s[0]
和 s[3], s = "bcad"
交换s[1]
和 s[2], s = "bacd"
因为要求字典序最小,那我们只需要将所有可以交换的位置上的字符从小到大重新排序。
思路:
设 i < j < k
, s[i]
和s[j]
可以交换,,s[j]
和s[k]
也可以交换。
则根据传递性,s[i]
和s[k]
也可以交换,
则可以将相互交换的都放入一个集合中,然后在排序。
输出的时候依次找到当前字符属于的集合 并且这个字符所对应的下标的相对位置是集合中的第几位
妥妥的 并查集
需要三个辅助数组:
fa[]
并查集中的 祖先数组
string str[]
用来存储所有属于同一个集合的字符
cnt[]
cnt[i]
表示的是输出的时候str[find(i)]
当前需要输出第几个数字,
同一个集合里面的字符只能用一次,find(i)
指的是当前i
属于的集合
Step1: 初始化
idx 0 1 2 3
s = d c a b
fa[] 0 1 2 3 // fa[x] = y, x集合的祖先是y 最开始每个位置上的字符的祖先都是自己
--------------------------------------------
Step2: 合并集合,将可以相互交换的下标都放入同一个集合中
pairs数组
pairs[0] = [0 , 3] // fa[find(0)] = find(3) 讲0属于的集合 划分到3的范围内
此时
s = d c a b
fa[] 3 1 2 3
pairs[1] = [1 , 2] // fa[find(1)] = find(2) 讲1属于的集合 划分到2的范围内
此时
s = d c a b
fa[] 3 2 2 3
--------------------------------------------
Step3: 将属于同一个集合的字符 放入同一个字符串内
for i in [0 , 3]:
str[find[i]] += s[i]
s = d c a b
fa[] 3 2 2 3
i = 0 find[0] = 3
str[3] = d
i = 1 find[1] = 2
str[2] = c
i = 2 find[2] = 2
str[2] = ca
i = 3 find[3] = 3
str[3] = db
--------------------------------------------
Step4: 将所有的字符串都从大到小排序。
str[0] = ""
str[1] = ""
str[2] = "ca" -----> str[2] = "ac"
str[2] = "db" -----> str[2] = "bd"
--------------------------------------------
Step5: 输出即可
for i in [0, 3]:
// 先找到i所属于的集合对应的字符串 再找到当前字符串该输出第几个
s[i] = str[find(i)][cnt[find(i)] ++ ]
return s
代码:
class Solution {
public:
vector<int > fa;
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
fa.resize(n);
string str[n];
vector<int > cnt(n);
for(int i = 0; i < n; ++ i){
fa[i] = i;
}
for(auto &p : pairs){
fa[find(p[0])] = find(p[1]); // p[0] 的 父亲 是 p[1]
}
for(int i = 0; i < n; ++ i){
// 在属于同一个集合里面的字符 合并成同一个字符串
str[find(i)] += s[i];
}
// for(int i = 0; i < n; ++ i){
// cout << i << " --- " << str[i] << endl;
// }
for(int i = 0; i < n; ++ i){
sort(str[i].begin(), str[i].end());
}
for(int i = 0; i < n; ++ i){
s[i] = str[find(i)][cnt[find(i)]++];
}
return s;
}
};