leetcode 1202. Smallest String With Swaps
You are given a string s, and an array of pairs of indices in the string pairs where pairs = indicates 2 indices(0-indexed) of the string.You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.
Example 1:
Input: s = "dcab", pairs = [,]
Output: "bacd"
Explaination:
Swap s and s, s = "bcad"
Swap s and s, s = "bacd"
Example 2:
Input: s = "dcab", pairs = [,,]
Output: "abcd"
Explaination:
Swap s and s, s = "bcad"
Swap s and s, s = "acbd"
Swap s and s, s = "abcd"
Example 3:
Input: s = "cba", pairs = [,]
Output: "abc"
Explaination:
Swap s and s, s = "bca"
Swap s and s, s = "bac"
Swap s and s, s = "abc"
Constraints:
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs, pairs < s.length
s only contains lower case English letters.
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int len = s.length();
UnionFind u = new UnionFind(len);
for(List <Integer> list: pairs){
u.union(list.get(0),list.get(1));
}
Map <Integer, List<Character>> map = new HashMap<>();
for(int i = 0; i <len; i++){
int head = u.find(i);
List<Character> cha = map.computeIfAbsent(head, k -> new ArrayList<>());
cha.add(s.charAt(i));
}
for(List<Character> c : map.values()){
Collections.sort(c);
}
StringBuilder re = new StringBuilder();
Map <Integer,Integer> help = new HashMap<>();
for(int i = 0 ; i< len; i++){
int x =u.find(i);
List<Character> list = map.get(x);
help.put(x, help.getOrDefault(x,-1)+1);
char aa = list.get(help.get(x));
re.append(aa);
}
return re.toString();
}
public class UnionFind{
int[] parent;
int[] size;
public UnionFind(int x){
parent = new int;
size = new int;
for(int i = 0; i < x ; i++){
size = 1;
parent = i;
}
}
public int find(int x){
int root = x;
while(root != parent){
parent = parent];
root = parent;
}
return root;
}
public int union(int x, int y){
int rootx = find(x);
int rooty = find(y);
if(rootx == rooty){
return size;
}
if(size > size){
parent = rootx;
size = size + size;
return size;
}
else if(size < size){
parent = rooty;
size = size + size;
return size;
}
else{
parent = rooty;
size = size + size;
return size;
}
}
}
}
页:
[1]