질문 집합: LeetCode: 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 에는 소문 자 영문 자모 만 포함 되 어 있 습 니 다.
문제 풀이 의 사고 방향.
/ / 문제 풀이 방향 은 연 결 된 변 을 하나의 집합 에 넣 고 모든 집합 에 있 는 문 자 를 정렬 하면 가장 작은 사전 순 서 를 얻 을 수 있 습 니 다. /어 려 운 점 은 같은 집합 에 있 는 문 자 를 어떻게 정렬 하고 정렬 한 후에 원래 문자열 을 어떻게 삽입 하 는 지 에 있다.이 문 제 는 Hashmap, char 배열, sb 로 완성 합 니 다.
2 코드 구현

class Solution {
     
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
     
        DisJU dju = new DisJU(100000 + 5);
        // pair             
        for (List<Integer> list : pairs) {
     
            dju.union(list.get(0), list.get(1));
        }
        //              key,        List   。
        HashMap<Integer, List<Integer>> hs = new HashMap<>();
        for (int i = 0; i < s.length(); ++i) {
     
            int key = dju.find(i);
            hs.computeIfAbsent(key, k -> new ArrayList<>()).add(i);//  list   ，newList  add
        }
        //       ，  sb
        StringBuilder sb = new StringBuilder(s);
        for (List<Integer> idx_list : hs.values()) {
     
            if (idx_list.size() > 1) {
     
                //mysort                      char    ，   ，            。
                mysort(sb, idx_list);
            }
        }
        return sb.toString();
    }
    private void mysort(StringBuilder sb, List<Integer> idx_list) {
     
        //        ，    char  ，      ，sort  ，null        ，                。
//        char[] chars = new char[sb.length()];
//        for (int idx:idx_list){
     
//            chars[idx] = sb.charAt(idx);// char    idx   sb    
//        }
//        Arrays.sort(chars);
//        for (int idx:idx_list){
     
//            sb.setCharAt(idx,chars[idx]);
//        }
//    }
        char[] chars = new char[idx_list.size()];
        for (int i = 0; i < idx_list.size(); ++i) {
     
            chars[i] = sb.charAt(idx_list.get(i));
        }
        Arrays.sort(chars);
        for (int i = 0; i < idx_list.size(); ++i) {
     
            sb.setCharAt(idx_list.get(i), chars[i]);
        }

    }
}

class DisJU{
     
    int[] pre;
    public DisJU(){
     }
    public DisJU(int n){
     
        pre = new int[n];
        for (int i=0;i<n;++i){
     
            pre[i]=i;
        }
    }
    public int find(int x ){
     
        if (pre[x]==x)return x;
        int root = find(pre[x]);
        return pre[x]=root;
    }
    public void union(int a ,int b){
     
        int x = find(a);
        int y = find(b);
        pre[x]=y;
    }
}