响应式网站底部菜单栏/jsurl转码

给你一个字符串 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^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s 中只含有小写英文字母

解题思路

这个题目乍一看很难先手，我们不方法将给的例子过一遍。首先第一个例子

接着第二个例子

我们此时发现根据pairs可以将s中的不同字符联系起来，实际上我们可以将联系在一起的字符串看成是一个集合，然后对这个集合从小到大排序，最后再按照原先的位置将各个字符放回去，那么此时所构成的字符串一定是可以通过pairs转换后字典序最小的那个。说到这，其实就不难想到并查集了。

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] = pymem = 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)

算法思路非常清晰，首先遍历pairs通过并查集确定集合，然后对相同集合的字符进行排序，最后将字符归位。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！