1202. 交换字符串中的元素(并查集)
1202. 交换字符串中的元素
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 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
提示：
1 <= s.length <= 10^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengths中只含有小写英文字母
1 class UinionFindeSet { 2 public: 3 void init(int n) { 4 parent.resize(n); 5 rank.resize(n); 6 for (int i = 0; i < n; i++) { 7 parent[i] = i; 8 rank[i] = 1; 9 } 10 return; 11 } 12 int findRoot(int x) { 13 int root = x; 14 // 找出x所属的根节点 15 while (root != parent[root]) { 16 root = parent[root]; 17 } 18 // 路径压缩 19 while (x != root) { 20 int next = parent[x]; 21 parent[x] = root; 22 x = next; 23 } 24 return root; 25 } 26 bool isConnected(int x, int y) { 27 return (findRoot(x) == findRoot(y)); 28 } 29 void unify(int x, int y) { 30 if (isConnected(x, y)) { 31 return; 32 } 33 int xRoot = findRoot(x); 34 int yRoot = findRoot(y); 35 if (parent[xRoot] <= parent[yRoot]) { 36 parent[xRoot] = yRoot; 37 rank[yRoot]++; 38 } else { 39 parent[yRoot] = xRoot; 40 rank[xRoot]++; 41 } 42 return; 43 } 44 private: 45 vector<int> parent; // 存储节点的根节点 46 vector<int> rank; // 同属于同一个根节点下的节点的个数 47 }; 48 class Solution : public UinionFindeSet { 49 public: 50 string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) { 51 if (pairs.size() == 0) { 52 return s; 53 } 54 int n = s.size(); 55 // 1、初始化并查集 56 init(n); 57 // 2、合并存在交集的交换对 58 for (auto &pair : pairs) { 59 unify(pair[0], pair[1]); 60 } 61 // 3、建立代表元与同属于同一代表元字符集的映射,key->字符所属的代表元,value->该代表元下的所有字符集 62 unordered_map<int, vector<char>> hashMap; 63 hashMap.reserve(26); // key值为小写英文字符,hash表最大容量为26 64 for (int i = 0; i < n; i++) { 65 hashMap[findRoot(i)].push_back(s[i]); 66 } 67 // 4、对同一代表元下的字符集降序排列 68 for (auto &pair : hashMap) { 69 sort(pair.second.begin(), pair.second.end(), [](int x, int y) { 70 return x > y; 71 }); 72 } 73 // 5、重组字符串s 74 for (int i = 0; i < n; i++) { 75 int root = findRoot(i); 76 s[i] = hashMap[root].back(); 77 hashMap[root].pop_back(); 78 } 79 return s; 80 } 81 };