Leetcode 1202. Smallest String With Swaps

[Woodyiiiiiii]

使用并查集解法；稍微变化的是，每个并查集内部按题目所给顺序排序，最终合并组合成一个字符串：

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        
        int n = s.length();
        UnionSet unionSet = new UnionSet(n);

        for (List<Integer> pair : pairs) {
            unionSet.union(pair.get(0), pair.get(1));
        }

        Map<Integer, Queue<Character>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(unionSet.find(i), k -> new PriorityQueue<>()).add(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(unionSet.find(i)).poll());
        }

        return sb.toString();
    }
}

class UnionSet {

    private int[] f;

    private int n;

    public UnionSet(int n) {
        this.n = n;
        f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }

    public int find(int x) {
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    public void union(int x, int y) {
        int xr = find(x);
        int yr = find(y);
        if (xr != yr) {
            f[xr] = yr;
        }
    }

}