问题描述
给你一个字符串 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”
分析
审题可以发现，pairs是给定的成对的可交换的位置。另外，如果两对可交换的集合有交集的话，例如[1, 2]和[2, 3]，那么下标为1、2、3的三个数可以交换成任意顺序，自然就可以交换得到这三个字符能够组成的字典序最小的字符串。那么多几对都有交集的情况呢？通过观察也是这样的，所以我们可以通过并查集的方法，来将这些索引对看成是集合，有交集的可以联通在一起，通过并查集将它们有交集的归为一个集合。假设得到三个集合，我们只需要分别对三个集合排序（使用优先队列）就可以了，最后从下标0开始遍历，每次取该下标所属集合的最小的那个字符即可，选取后同时将其从该集合的优先队列中弹出。
class Solution {
// 并查集
int[] pre;
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
if (pairs.size() == 0)
return s;
int len = s.length();
pre = new int[len];
for (int i = 0; i < len; i++) {
pre[i] = i;
}
// 使用并查集进行划分
for (int i = 0; i < pairs.size(); i++) {
union(pairs.get(i).get(0), pairs.get(i).get(1));
}
// 并查集中每个集合都有个root，将该集合中的字符通过优先队列进行排序
Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
for (int i = 0; i < len; i++) {
int root = find(i);
if (map.containsKey(root)) {
map.get(root).offer(s.charAt(i));
} else {
PriorityQueue<Character> heap = new PriorityQueue<>();
heap.offer(s.charAt(i));
map.put(root, heap);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
int root = find(i);
sb.append(map.get(root).poll());
}
return sb.toString();
}
public int find(int root) {
if (pre[root] == root) {
return root;
}
return pre[root] = find(pre[root]);
}
public void union(int a, int b) {
int x = find(a);
int y = find(b);
if (x != y) {
pre[x] = y;
}
}
}
