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.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"
Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
Example 3:
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"
使用 union find 给下标分组，相同的组压入堆中进行排序。union find 需要将每个节点在 find 的时候连接到根节点，不然会超时。
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int len=s.length();
HashMap<Integer,PriorityQueue<Character>> map=new HashMap<>();
char[] arr=s.toCharArray();
//If unionFind[i]==i , i is a root node, or i is connected to unionFind[i]
//Try to group indexes to different groups
int[] unionFind=new int[len];
for(int i=0;i<len;++i){
unionFind[i]=i;
}
for(List<Integer> list:pairs){
int i1=list.get(0);
int i2=list.get(1);
//connect 2 groups to 1
union(unionFind, i1, i2);
}
for(int i=0;i<len;++i){
//each index is connected to a root id
int id=find(unionFind,i);
//each id has a priority queue
map.computeIfAbsent(id, key->new PriorityQueue<>()).add(arr[i]);
}
for(int i=0;i<len;++i){
int id=find(unionFind,i);
arr[i]=map.get(id).poll();
}
return String.valueOf(arr);
}
/*
This function is able to find the root but cause time limit exceeded
private int find(int[] uf, int index){
while(uf[index]!=index) index=uf[index];
return index;
}
*/
private int find(int[] uf, int index){
int i=uf[index];
if(index==i) return index;
// set all node connected to root
uf[index]=find(uf, i);
return uf[index];
}
//quick-union
private void union(int[] uf, int u, int v){
int uRoot=find(uf, u);
int vRoot=find(uf, v);
uf[uRoot]=vRoot;
}
}
最开始不会 union find 的时候的解法：
class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int len=s.length();
char[] arr=s.toCharArray();
ArrayList<TreeSet<Integer>> list=getAllSwaps(pairs,len);
for(TreeSet<Integer> set:list){
swap(arr,set);
}
return String.valueOf(arr);
}
private ArrayList<TreeSet<Integer>> getAllSwaps(List<List<Integer>> pairs, int len){
ArrayList<Integer>[] lists=new ArrayList[len];
for(int i=0;i<len;++i) lists[i]=new ArrayList<>();
for(List<Integer> l:pairs){
Integer i1=l.get(0);
Integer i2=l.get(1);
lists[i1].add(i2);
lists[i2].add(i1);
}
boolean[] visited=new boolean[len];
ArrayList<TreeSet<Integer>> ret=new ArrayList<>();
for(int i=0;i<len;++i){
if(!visited[i] && lists[i].size()>0){
TreeSet<Integer> set=new TreeSet<>();
ret.add(set);
recur(set, i, visited, lists);
}
}
return ret;
}
private void recur(Set<Integer> set, int index, boolean[] visited,
ArrayList<Integer>[] lists){
visited[index]=true;
ArrayList<Integer> list=lists[index];
for(Integer i:list){
set.add(i);
if(!visited[i]){
recur(set,i,visited,lists);
}
}
}
private void swap(char[] arr, TreeSet<Integer> set){
char[] toSwap=new char[set.size()];
int index=0;
for(Integer i:set){
toSwap[index++]=arr[i];
}
Arrays.sort(toSwap);
index=0;
for(Integer i:set){
arr[i]=toSwap[index++];
}
}
}