LeetCode 1202. 交换字符串中的元素

题目描述

1202. 交换字符串中的元素

解法：并查集（C++）

首先要理解一个点：如果把字符抽象为一个图顶点，那么能交换即代表两个图顶点之间连通，而对于一个连通分量，其所含的顶点表示的字符是任意可交换的

既然提到了连通分量，就很容易知道为什么要使用并查集了

下面是 LeetCode 的官方题解

class DisjointSetUnion {
    
private:vector<int> f, rank;int n;public:DisjointSetUnion(int _n) {
    n = _n;rank.resize(n, 1);f.resize(n);for (int i = 0; i < n; i++) {
    f[i] = i;}}int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);}void unionSet(int x, int y) {
    int fx = find(x), fy = find(y);if (fx == fy) {
    return;}if (rank[fx] < rank[fy]) {
    swap(fx, fy);}rank[fx] += rank[fy];f[fy] = fx;}
};class Solution {
    
public:string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
    DisjointSetUnion dsu(s.length());for (auto& it : pairs) {
    dsu.unionSet(it[0], it[1]);}unordered_map<int, vector<int>> mp;for (int i = 0; i < s.length(); i++) {
    mp[dsu.find(i)].emplace_back(s[i]);}for (auto& [x, vec] : mp) {
    sort(vec.begin(), vec.end(), greater<int>());}for (int i = 0; i < s.length(); i++) {
    int x = dsu.find(i);s[i] = mp[x].back();mp[x].pop_back();}return s;}
};