leetcode 1202. Smallest String With Swaps

Seawolf

1. You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
   
2. 
   
3. You can swap the characters at any pair of indices in the given pairs any number of times.
   
4. 
   
5. Return the lexicographically smallest string that s can be changed to after using the swaps.
   
6. 
   
7. 
   
8. 
   
9. Example 1:
   
10. 
    
11. Input: s = "dcab", pairs = [[0,3],[1,2]]
    
12. Output: "bacd"
    
13. Explaination:
    
14. Swap s[0] and s[3], s = "bcad"
    
15. Swap s[1] and s[2], s = "bacd"
    
16. Example 2:
    
17. 
    
18. Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
    
19. Output: "abcd"
    
20. Explaination:
    
21. Swap s[0] and s[3], s = "bcad"
    
22. Swap s[0] and s[2], s = "acbd"
    
23. Swap s[1] and s[2], s = "abcd"
    
24. Example 3:
    
25. 
    
26. Input: s = "cba", pairs = [[0,1],[1,2]]
    
27. Output: "abc"
    
28. Explaination:
    
29. Swap s[0] and s[1], s = "bca"
    
30. Swap s[1] and s[2], s = "bac"
    
31. Swap s[0] and s[1], s = "abc"
    
32. 
    
33. 
    
34. 
    
35. Constraints:
    
36. 
    
37. 1 <= s.length <= 10^5
    
38. 0 <= pairs.length <= 10^5
    
39. 0 <= pairs[i][0], pairs[i][1] < s.length
    
40. s only contains lower case English letters.

复制代码

1. class Solution {
   
2.     public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
   
3.         int len = s.length();
   
4.         UnionFind u = new UnionFind(len);
   
5.         for(List <Integer> list: pairs){
   
6.             u.union(list.get(0),list.get(1));
   
7.         }
   
8.         
   
9.         Map <Integer, List<Character>> map = new HashMap<>();
   
10.         for(int i = 0; i <len; i++){
    
11.             int head = u.find(i);
    
12.             List<Character> cha = map.computeIfAbsent(head, k -> new ArrayList<>());
    
13.             cha.add(s.charAt(i));
    
14.         }
    
15.         
    
16.         for(List<Character> c : map.values()){
    
17.             Collections.sort(c);
    
18.         }
    
19.         
    
20.         StringBuilder re = new StringBuilder();
    
21.         Map <Integer,Integer> help = new HashMap<>();
    
22.         for(int i = 0 ; i< len; i++){
    
23.             
    
24.             int x =u.find(i);
    
25.             List<Character> list = map.get(x);
    
26.             help.put(x, help.getOrDefault(x,-1)+1);
    
27.             char aa = list.get(help.get(x));
    
28.             re.append(aa);
    
29.         }
    
30.         return re.toString();
    
31.     }
    
32.    
    
33.     public class UnionFind{
    
34.         
    
35.         int[] parent;
    
36.         int[] size;
    
37.         
    
38.         public UnionFind(int x){
    
39.             parent = new int[x];
    
40.             size = new int[x];
    
41.             for(int i = 0; i < x ; i++){
    
42.                 size[i] = 1;
    
43.                 parent[i] = i;
    
44.             }
    
45.             
    
46.         }
    
47.         
    
48.         public int find(int x){
    
49.             int root = x;
    
50.             while(root != parent[root]){
    
51.                
    
52.                 parent[root] = parent[parent[root]];
    
53.                 root = parent[root];
    
54.             }
    
55.             return root;
    
56.         }
    
57.         
    
58.         public int union(int x, int y){
    
59.             int rootx = find(x);
    
60.             int rooty = find(y);
    
61.             
    
62.             if(rootx == rooty){
    
63.                 return size[rootx];
    
64.             }
    
65.             
    
66.             if(size[rootx] > size[rooty]){
    
67.                 parent[rooty] = rootx;
    
68.                 size[rootx] = size[rootx] + size[rooty];
    
69.                 return size[rootx];
    
70.             }
    
71.             else if(size[rootx] < size[rooty]){
    
72.                 parent[rootx] = rooty;
    
73.                 size[rooty] = size[rooty] + size[rootx];
    
74.                 return size[rooty];
    
75.             }
    
76.             else{
    
77.                 parent[rootx] = rooty;
    
78.                 size[rooty] = size[rooty] + size[rootx];
    
79.                 return size[rooty];
    
80.             }
    
81.         }
    
82.     }
    
83. }

复制代码