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; } } }
|