题目

题目来源：力扣（LeetCode）

给你一个字符串 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”

思路分析

根据给定的数组pairs，我们可以获取到可以交换的字母。然后将可交换的字母分别组成一组。对 组内的字母进行排序。然后根据字符串中字符的组号来获取组内的最小字符进行字符串拼接。最后得出 的字符串就是我们所需要的字符串。

  1. /**
  2.  * @param {string} s
  3.  * @param {number[][]} pairs
  4.  * @return {string}
  5.  */
  6. var smallestStringWithSwaps = function (s, pairs) {
  7.   // 获取字符串的长度
  8.   const len = s.length;
  9.   // 根据字符串的长度构建并查集
  10.   let uf = new UnionFind(len);
  11.   // 将可以交换的字符坐标进行连通
  12.   for (let i = 0; i < pairs.length; i++) {//拿到索引对，遍历索引对数组
  13.     let index1 = pairs[i][0], index2 = pairs[i][1];//拿到里面的每一对数组
  14.     if (uf.findSet(index1) != uf.findSet(index2)) {//拿到这两个索引，去给他联通上
  15.       uf.unite(index1, index2);
  16.     }
  17.   }
  18.   // 获取连通后的数组
  19.   let fa = uf.parent;
  20.   //将连通的字符存入到一个数组中并进行排序。
  21.   let vec = new Array(len).fill(0).map(() => new Array());//根据祖先节点分组，value 是组里面字符串的结合；字符串的特性是由小到大排序，用一个小根堆
  22.   for (let i = 0; i < len; i++) {
  23.     fa[i] = uf.findSet(i);
  24.     vec[fa[i]].push(s[i]);
  25.   }
  26.   for (let i = 0; i < len; i++) {
  27.     if (vec[i].length > 0) {
  28.       vec[i].sort((a, b) => a.charCodeAt() - b.charCodeAt());
  29.     }
  30.   }
  31.   //记录每组取字符的位置
  32.   let p = new Array(len).fill(0);
  33.   // 输出字符的数组
  34.   let ans = [];
  35.   for (let i = 0; i < len; ++i) {
  36.     ans.push('1');
  37.   }
  38.   //通过原始字符坐标获取字符的组号然后进行取字符拼接
  39.   for (let i = 0; i < len; ++i) {
  40.     ans[i] = vec[fa[i]][p[fa[i]]];
  41.     p[fa[i]]++;
  42.   }
  43.   // 拼接字符
  44.   return ans.join('');
  45. };
  48. // 并查集
  49. class UnionFind {
  50.   constructor(n) {
  51.     // 元素所指向的父节点，parent[i] 表示第 i 个元素所指向的父节点
  52.     // 初始化时, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
  53.     this.parent = new Array(n).fill(0).map((value, index) => index);
  54.     // 树的层数，rank[i] 表示以 i 为根的集合所表示的树的层数
  55.     this.rank = new Array(n).fill(1);
  56.     // 节点的个数
  57.     this.setCount = n;
  58.   }
  60.   // 查找过程，查找元素 index 所在集合的编号(查找树的根节点)
  61.   findSet(index) {
  62.     // 不断去查询自己的父节点，直至根节点
  63.     // 根节点的标志是父节点就是本身  parent[index] == index
  64.     if (this.parent[index] != index) {
  65.       // 递归获取节点的父节点
  66.       this.parent[index] = this.findSet(this.parent[index]);
  67.     }
  68.     // 返回根节点
  69.     return this.parent[index];
  70.   }
  72.   // 合并两个集合
  73.   unite(index1, index2) {
  74.     let root1 = this.findSet(index1);
  75.     let root2 = this.findSet(index2);
  76.     // 根节点不一样，是两个不同的集合(两棵不同的树)
  77.     if (root1 != root2) {
  78.       // 根据树的层数合并集合
  79.       // 
  80.       if (this.rank[root1] < this.rank[root2]) {
  81.         // 这个判断如果 root2 所在树的层数 大于 root1，就交换两个父节点，这样始终让 root1 为父节点
  82.         [root1, root2] = [root2, root1];
  83.       }
  84.       // 将层数多的集合合并到集合少的集合
  85.       this.parent[root2] = root1;
  86.       this.rank[root1] += this.rank[root2];
  87.       this.setCount--;
  88.     }
  89.   }
  91.   getCount() {
  92.     return this.setCount;
  93.   }
  95.   connected(index1, index2) {
  96.     return this.findSet(index1) === this.findSet(index2);
  97.   }
  98. }