1202. 交换字符串中的元素

发表于 | 分类于
并查集学习

主要是用来学习并查集的思路，看了答案才下手的。

思路就是先对可交换的字符串进行分组，分组排序之后再组合起来

并查集就是用递归或者while循环实现find ， 然后 再用数组和下标的方式实现union

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var smallestStringWithSwaps = function(s, pairs) {
  var fa = []
  var find = function (x) {
    if (x === fa[x]) {
      return x
    } else {
      return fa[x] = find(fa[x])
    }
  }
  for (let i = 0; i < s.length; i++) {
      fa[i] = i
  }
  for(let i = 0 ; i < pairs.length ; i ++) {
    const [x,y] = pairs[i]
    fa[find(x)] = find(y)
  }
  var n = s.length
  // 计算分组后的map
  const vec = new Array(n).fill(0).map(() => new Array());
  for (let i = 0; i < n; i++) {
      
      fa[i] = find(i);
      vec[fa[i]].push(s[i]);
  }
  console.log(fa)
  // 对分组后的map 进行排序
  for (let i = 0; i < n; ++i) { 
      if (vec[i].length > 0) {
          vec[i].sort((a, b) => a.charCodeAt() - b.charCodeAt());
      }
  }
  // 组合成ans
  const ans = new Array(n).fill(0);
  for (let i = 0; i < n; ++i) {
      var group = fa[i]
      if ( group!= undefined && vec[group].length) {

        // 取出每个组中序号最小的
        ans[i] = vec[fa[i]].shift()
      } else {
        ans[i] = s[i]
      }
  }
  return ans.join('')
};