首先处理 pairs,可以将数组分成多个连通块 然后每个连通块分别排序 这里由于 s 中只有 小写字母, 所以排序可以利用桶排序的思想
复杂度分析 时间复杂度:O(n),桶排序所需时间 空间复杂度:O(n)
class Solution {
int[] p = new int[(int)2e5 + 10];
private int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int[][] map = new int[s.length()][26];
for (int i = 0; i < p.length; i++) p[i] = i;
for (List<Integer> pp : pairs) {
int px = find(pp.get(0));
int py = find(pp.get(1));
p[px] = py;
}
for (int i = 0; i < s.length(); i++) {
map[find(i)][s.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < map.length; i++) {
int[] table = map[find(i)];
for (int k = 0; k < table.length; k++) {
if (table[k] > 0) {
sb.append((char) (k + 'a'));
table[k]--;
break;
}
}
}
return sb.toString();
}
}