1202. Smallest String With Swaps

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.

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.

并查集,注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组,借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
StringBuffer sb = new StringBuffer();
UnionFind uf = new UnionFind(s.length());

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

int[] group = new int[s.length()];
for(int i = 0; i < s.length(); i++){
group[i] = uf.find(i);
}

HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();

for(int i = 0; i < s.length(); i++){
PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
bin.add(s.charAt(i));
map.put(group[i], bin);
}
for(int i = 0; i < s.length(); i++){
sb.append(map.get(group[i]).poll());
}
return sb.toString();
}

class UnionFind {
int[] parent;
int[] count;
public UnionFind(int n){
parent = new int[n];
count = new int[n];
for(int i = 0; i < n; i++){
parent[i] = i;
count[i] = 1;
}
}

private int find(int id){
if(parent[id] == id) return id;
parent[id] = find(parent[id]);
return parent[id];
}

private boolean union(int id1, int id2){
int p1 = find(id1);
int p2 = find(id2);
if(p1 == p2) return false;
if(count[p1] > count[p2]) parent[p2] = p1;
else parent[p1] = p2;
return true;
}
}
}
Author

Xander

Posted on

2022-04-27

Updated on

2022-06-25

Licensed under

Comments