1202. Smallest String With Swaps

问题：

给定字符串s，和可进行交换的index对数组。

对字符串s的各个位置index，可根据交换数组所示的两两交换（次数不限），求进行交换后，可得最小的字符串。

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"
 
Constraints:
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

　　

解法：

本问题为：连通图问题，

对两组可交换的index对，出现重复index的话，那么这两个组之间的3个index都可以任意交换。

那么，题意可转换为：

在给出的可交换对数组中，可形成多个可任意交换的index序列，

这几个序列之间没有交集，但是序列内部可进行随意排序，

求出每个序列的最小排序，并将这些序列合并。

本问题的关键：连通图的构造

方法一：

dfs：深度优先排序：

对图中的每一个未访问过的节点a（一个连通图），轮询：

    对每个节点a 的邻接点 adjList，依次轮询标记，标记为一个组。graphid

    访问过的节点，要标记 visited

最后，graphid相同的即为一个连通图。

这里，对每一个连通图，要做固定操作的话，可在标记graphid的同时，直接进行操作。

（对于本题，则是记录：当前连通图的节点 idx[] ）

（在每一个连通图遍历完毕的时候，对重新取得节点对应的字符，组成新的字符串tmp，对tmp排序，再将新的排序赋值回原字符串s中）

代码参考：

class Solution {
public:
    vector<bool> visited;
    vector<vector<int>> adjList;
    string tmp;
    vector<int> idx;
    
    void dfs(int i, string& s){
        visited[i]=true;//marked->0 设置访问
        tmp.push_back(s[i]);
        idx.push_back(i);//同一层连通图
        for(int p:adjList[i]){
            if(!visited[p]){//marked==0 未访问过
                dfs(p, s);
            }
        }
    }
    string makepinfo(string& s){
        string res(s.length(),0);
        for(int i=0; i<s.length(); i++){
            tmp="";
            idx.clear();
            if(!visited[i]){//未访问过
                dfs(i, s);
                sort(tmp.begin(), tmp.end());
                sort(idx.begin(), idx.end());
                for(int t=0; t<tmp.size(); t++){
                    res[idx[t]]=tmp[t];
                }
            }
        }
        return res;
    }
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        visited.resize(s.length(),false);
        adjList.resize(s.length());
        for(auto p:pairs){
            adjList[p[0]].push_back(p[1]);
            adjList[p[1]].push_back(p[0]);
        }
        return makepinfo(s);
    }
};

方法二：

直接使用

数组vector un表示是否为一个连通图：

un[i]：元素i的邻接元素。

        UN(int n){//初始化连通组，自己的下一个为自己，每个元素孤立存在
            un.resize(n);
            for(int u=0; u<n; u++){
                un[u]=u;
            }
        }

un.unite(i, j)：链接两个元素。

（使用find，寻找两个节点的终点）

（如果终点相同，说明两元素已经在同一个连通图中）

（否则，将 i 的终点 un[fi] 指向 j ）

        void unite(int i, int j){//合并连通组 i和j
            int fi=find(i);
            int fj=find(j);
            if(fi!=fj){//两个连通图的终点不一样，则合并连通图i和j
                un[fi]=j;
            }//否则，i和j是连通图
        }

un.find(i)：找到元素i所在连通图的终点节点。

        int find(int i){
            int x=un[i];
            if(un[x]!=x){
                un[i]=find(x);
            }
            return un[i];
        }

那么对于本题，首先构造un

对每一对pair，进行unite。

构造完毕后，构造连通图组group

key：连通图终点元素，value：连通图的各个节点。

        unordered_map<int, vector<int>> group;
        //使用连通图UN，做成连通图组，key：UN每个连通图的终点，value：连通图的各个节点
        for(int i=0; i<N; i++){
            group[un.find(i)].push_back(i);
        }

然后遍历每个连通图，进行string tmp排序

并合并各个tmp的动作。

        //使用group排序每个连通图的string
        for(auto g:group){
            string tmp("");
            for(int idx:g.second){
                tmp.push_back(s[idx]);
            }
            sort(tmp.begin(), tmp.end());
            int i=0;
            for(int idx:g.second){
                s[idx]=tmp[i];
                i++;
            }
        }

总代码参考：

class Solution {
public:
    class UN {
        public:
        vector<int> un;
        UN(int n){//初始化连通组，自己的下一个为自己，每个元素孤立存在
            un.resize(n);
            for(int u=0; u<n; u++){
                un[u]=u;
            }
        }
        int find(int i){
            int x=un[i];
            if(un[x]!=x){
                un[i]=find(x);
            }
            return un[i];
        }
        void unite(int i, int j){//合并连通组 i和j
            int fi=find(i);
            int fj=find(j);
            if(fi!=fj){//两个连通图的终点不一样，则合并连通图i和j
                un[fi]=j;
            }//否则，i和j是连通图
        }
    };
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int N=s.length();
        UN un(N);
        for(auto p:pairs){//使用pairs，做成连通图UN
            un.unite(p[0], p[1]);
        }
        unordered_map<int, vector<int>> group;
        //使用连通图UN，做成连通图组，key：UN每个连通图的终点，value：连通图的各个节点
        for(int i=0; i<N; i++){
            group[un.find(i)].push_back(i);
        }
        //使用group排序每个连通图的string
        for(auto g:group){
            string tmp("");
            for(int idx:g.second){
                tmp.push_back(s[idx]);
            }
            sort(tmp.begin(), tmp.end());
            int i=0;
            for(int idx:g.second){
                s[idx]=tmp[i];
                i++;
            }
        }
        return s;
    }
};