社区首页 >专栏 >并查集经典题解——交换字符串中的元素

并查集经典题解——交换字符串中的元素

用户6557940

发布于 2022-07-24 08:39:24

51700

代码可运行

文章被收录于专栏：Jungle笔记Jungle笔记

运行总次数：0

代码可运行

如果刷朋友圈的时候你还不知道并查集，那么可以看看这篇：

每天都刷朋友圈，那你知道并查集吗？

在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;
}