LeetCode上交换字符串中的元素，中等难度，记录下解题思路
这里要用到查并集的做法，可以参考之前省份数量的解题思路，假设传入参数s = "dcab", pairs = [[0,3],[1,2],[0,2]]。
首先对传入的pairs双重数组构建关系图，可以看出[0,3,2]和[1,2]中间是有关系的，可以视为4个元素之间都有关系，根据题意可以随意交换，只需要将整个字符串所有字符从小到大排序即可
整个题的操作有两步：
- 确定哪几个字符之间可以随意交换
- 如何拼接字符串
确立字符之间的关系
首先创建字符串长度多个节点，把这些节点的parent属性设置为自己
然后根据pairs数组，把几个节点连接起来。
连接的时候就在做路径压缩，把节点都连接到同一个根节点之上
之后通过Map根据根节点不同保存不同的数据，对不同数据进行排序，这样每个小区间都是从小到大排列
如何拼接字符串
根据当前节点的parent在设定好的Map中间取值拼接
class node {
constructor (s) {
// 创建的节点都把自己的父亲先设为自己
this.parent = this
// 设置节点对应的字符串的值
this.val = s
}
}
var smallestStringWithSwaps = function(s, pairs) {
let slen = s.length
let plen = pairs.length
let nodes = []
let m = new Map()
let res = ''
let find = function (x) {
if (x !== x.parent)
return find(x.parent)
return x.parent
}
for(let i = 0; i<slen; i++) {
// 创建多个节点
nodes.push(new node(i,s[i]))
}
// 通过传入的数据更改当前元素的parent属性
function change(x,y) {
// 要将y的parent属性设为x，传入的是pairs里面的数组
find(nodes[y]).parent = find(nodes[x])
}
// 循环pairs数组生成对应关系
for(let i=0; i<plen; i++) {
//每次取出的是二维数组
let [x,y] = pairs[i]
change(x,y)
}
for (let i = 0; i < slen; i++) {
let f = find(nodes[i]);
if(m.has(f)) {
m.get(f).push(s[i])
} else {
m.set(f,[s[i]])
}
}
m.forEach((item) => {
item.sort((a, b) => a.charCodeAt() - b.charCodeAt())
})
for (let i = 0; i < slen; i++) {
let f = find(nodes[i]);
// 每次取集合中首位元素，并删除
res += m.get(f).shift();
}
return res
};
