1202. Smallest String With Swaps

Link

Solution

public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int[] map = new int[s.length()];
        
        for(int i = 0; i < map.length; i++){
            map[i] = i;
        }
        
        for(List<Integer> pair : pairs){
            union(map, pair.get(0), pair.get(1));
            //union之後不能確保每個map直都是最後的root, 但資訊已可以追查出root
        }
        
        HashMap<Integer, PriorityQueue<Character>> hashmap = new HashMap<>();
        
        for(int i = 0; i < map.length; i++){
            int p = find(map, i); //要再次find才能確保map值都是root
            if(!hashmap.containsKey(map[i])){
                hashmap.put(map[i], new PriorityQueue<Character>());
            }
            
            hashmap.get(map[i]).add(s.charAt(i));
            
        }
        
        char[] res = s.toCharArray();
        
        for(int i = 0; i < res.length; i++){
            res[i] = hashmap.get(map[i]).poll();
        }
        
        return new String(res);
    }
    
    public int find(int[] map, int a){
        if(map[a] != a)
        {
            map[a] = find(map, map[a]);
        }
        return map[a];
    }
    
    
    public void union(int[] map, int a, int b){
        int aRoot = find(map, a);
        int bRoot = find(map, b);
        if(aRoot != bRoot){
            map[bRoot] = aRoot;
        }
        
    }