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

思路

随机到了之前做过的一个题，看来力扣的随机机制改了，可以出现做过的题目了（之前从来没有遇到过…

距离上次做已经时隔一年多了，只有一点点印象。去年做没有完全消化，现在能想到解法还是很庆幸哈哈

大致的思路就是，对于相互可以交换的一组（说一组是因为可以由好多数组共同组成）字符，将其按照字母顺序排序，然后依次放在这些位置。

那具体如何实现？我们可以用并查集维护相互连通的字符，然后使用一个哈希表记录每个连通分量中的字符集合，哈希表的为并查集的代表元，为连通分量，因为要实现排序，所以可以用优先队列，也方便后面构造结果字符串（方便是指添加一个字符就将其删除）。最后构造字符串时，对于每个下标，查找其代表元对应的优先队列，一个字符放在该下标。

具体实现细节见代码注释

代码

并查集+优先队列

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);
        for (List<Integer> pair : pairs) {
            // 并查集中存的是下标，不是字符，下标唯一而字符不唯一
            uf.union(pair.get(0), pair.get(1));
        }
        // key为并查集连通分量的代表元，value为该连通分量字符集合，使用优先队列方便排序
        // 对于s = "dcab", pairs = [[0,3],[1,2]]，如果0和1分别是代表元，那么map大致就是{0:[b,d], 1:[a,c]}
        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(uf.find(i), k -> new PriorityQueue<>()).offer(s.charAt(i));
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            // 使用优先队列，这里用掉一个字符，poll就行
            sb.append(map.get(uf.find(i)).poll());
        }
        return sb.toString();
    }
}
// 并查集类
class UnionFind {
    int[] parent;
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    // 查找p的代表元
    public int find(int p) {
        while (parent[p] != p) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    // 合并p和q
    public void union(int p, int q) {
        int proot = find(p);
        int qroot = find(q);
        if (proot == qroot) return;
        parent[proot] = qroot;
    }
}