1202. 交换字符串中的元素
给你一个字符串 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"
提示：
1 <= s.length <= 10^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.length-
s中只含有小写英文字母
解题思路：
设置字典存储，建立索引查找
1）将联系在一起的字符串看成是一个集合
2）对这个集合从小到大排序
3）按照原先的位置将各个字符放回去
故会采取并查集
代码：
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
p = list(range(len(s)))
def find(x):
if x != p[x]:
p[x] = find(p[x])
return p[x]
for i, j in pairs:
px, py = find(i), find(j)
if px != py:
p[px] = py
mem = collections.defaultdict(list)
for i, v in enumerate(p):
mem[find(v)].append(s[i])
for k in mem:
mem[k].sort(reverse=True)
res = []
for i in range(len(s)):
res.append(mem[find(i)].pop())
return "".join(res)
参考资料：
https://coordinate.blog.csdn.net/article/details/101281816?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.control
https://blog.csdn.net/qq_39180879/article/details/112463766
