并查集经典题解——交换字符串中的元素
如果刷朋友圈的时候你还不知道并查集，那么可以看看这篇：
在LeetCode上标签为“并查集”的题目不少，大部分题目在使用并查集后，解法一目了然，十分清晰，比如这篇文章要分析的一个题目——交换字符串中的元素。
看了题目给出的3个示例，更有助于我们理解题意：
示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]] 输出："bacd" 解释： 交换 s[0] 和 s[3], s = "bcad" 交换 s[1] 和 s[2], s = "bacd"
示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]] 输出："abcd" 解释： 交换 s[0] 和 s[3], s = "bcad" 交换 s[0] 和 s[2], s = "acbd" 交换 s[1] 和 s[2], s = "abcd"
示例 3：
输入：s = "cba", pairs = [[0,1],[1,2]] 输出："abc" 解释： 交换 s[0] 和 s[1], s = "bca" 交换 s[1] 和 s[2], s = "bac" 交换 s[0] 和 s[1], s = "abc"
比如我们分析示例2， s="dcab"，pairs = [[0,3],[1,2],[0,2]]。其中：
- pairs[0]=[0,3]——s中第0和第3个位置的字符可以交换位置（任意多次）。即“dcab”可以变成“bcad”，因为b比d小（排在字典序前面）。
- pairs[1]=[1,2]——s中第1和第2个位置的字符可以交换位置（任意多次）。即“dcab”可以变成“dacb”。结合着pairs[0]，即可变为"bacd"，因为a比c小。
- pairs[2]=[0,2]——s中第0和第2个位置的字符可以交换位置（任意多次）。注意结合pairs[0]，第0个字符和第3个字符可以互换位置，那么现在第0、2、3个字符都可以互换位置。再结合pairs[1]，第0、1、2、3都可以互换位置了。那根据题目要求，顺序排为“abcd”即可。
根据上面的分析，这道题可以分成两个步骤：
- 联合：查看pairs里哪些组合可以形成一个集合，比如[0,3]和[2,3]可以构成一个集合[0,2,3]；
- 排序：将集合中可交换的位置对应的字符按照字典序排序。比如[0,2,3]三个位置对应的字符d，a，b排序后卫a, b, d。
这个步骤中的联合，可以用并查集来实现。并查集怎么写呢？同样，可以先看这篇文章：每天都刷朋友圈，那你知道并查集吗？
class UnionFind{
private:
int n;
int *parent;
int *rank;
public:
UnionFind(int n){
this->n = n;
this->parent = new int[n];
this->rank = new int[n];
for (int i = 0; i < n; i++){
parent[i] = i;
rank[i] = 1;
}
}
~UnionFind(){
delete[]rank;
delete[]parent;
}
int find(int p){
while (p != parent[p]){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
bool isConnected(int p, int q){
return find(p) == find(q);
}
void unionElements(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] < rank[rootQ]){
parent[rootP] = rootQ;
}
else if (rank[rootQ] < rank[rootP]){
parent[rootQ] = rootP;
}
else{
parent[rootQ] = rootP;
rank[rootP] += 1;
}
}
};根据上述思路，本题题解如下：
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int size = s.length();
UnionFind uf(size);
// 1. 将可以互相交换位置的索引联合
for (int i = 0; i < pairs.size(); i++){
uf.unionElements(pairs[i][0], pairs[i][1]);
}
string res;
// 2. 将每个集合的索引对应位置的字符，存入一个数组
vector<vector<char>>v(size);
for (int i = 0; i < size; i++){
// 因为每个集合里的索引都指向同一个parent，所以用uf.find(i)来表示买个集合的索引
v[uf.find(i)].push_back(s[i]);
}
// 3. 排序：将每个集合里的字符按照字典序排序
for (int i = 0; i < v.size(); i++){
sort(v[i].rbegin(), v[i].rend());
}
// 4. 构造返回值
for (int i = 0; i < size; i++){
res += v[uf.find(i)].back();
v[uf.find(i)].pop_back();
}
return res;
}关于并查集，你还可以看：
- 130.被包围的区域
- 200.岛屿数量
- 684.多余连接
- ……
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读