[LeetCode] 1202. Smallest String With Swaps

[grandyang]

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"

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.

这道题给了一个字符串s，又给了一系列的 pair 对儿，里面是可以交换的坐标，这里的同一个交换对儿可以多次使用，当然也可以不使用，现在让求可以得到的字母顺序最小的字符串。博主最先拿到这道题的时候，觉得就是个类似于图遍历的题目，每种不同排列的字符串就是个不同的结点，需要找到那个字母顺序最小的那个结点。所以博主的做法就是使用 BFS 来做，用个 HashSet 来记录出现过的排列顺序，并且维护一个全局最小的排列顺序，就类似迷宫遍历中的上下左右四个新方向一样，只不过这里是根据 pair 对儿来交换某两个字母的位置，形成的新的排列顺序，用这个新的排列顺序来更新全局最小，并且只有当这个排列之前没有出现过，才加入队列 queue 中继续遍历。但是这样搞下来还是超时了 Time Limit Exceeded，看来这道题还得需要更加巧妙的解法才行啊。这里如果把s中的每个字母都看作一个结点的话，那么这里的 pair 对儿就相当于连接结点的边，若所有的结点都可以通过边来连通，那么结点值就可以任意调换，相当于直接给字符串排序，比如例子2和3。但若并不是任意两个结点都是连通时，比如例子1的情况，有两个独立的连通部分，则其相对的位置的关系还是得保留，每个连通内部是可以任意排序的。

所以这道题的一个关键点是在于对于每个连通部分单独处理，即最主要一点是要找到所有相连的结点，这可以用 DFS 来找，找到了所有相连结点的坐标值，放到一个数组中，同时也要将其对应的字母也都取出，分别进行排序，则此时最小的字母就可以对应到坐标最小的位置了。下面来看代码实现，首先是要建立图的结构，这里用一个二维数组g来以邻接链表的形式存储这个图的结构，对于每个 pair 对儿，由于是无向图，所以正反都要保存。接下来就要遍历每个字母结点了，为了避免重复遍历，这里用一个 visited 数组来记录访问过的结点，对于没有访问过的结点，新建一个数组 pos，用来保存所有和当前结点相连通的结点的位置坐标，然后调用递归函数。在递归函数中，首先将 visited 数组对应位置位置赋值为 true，同时把当前位置加入 pos 数组，然后就遍历和当前位置直接相连的结点了，若没有访问过，再对其调用递归函数即可。递归结束后，得到了 pos 数组，需要将对应位置上的字母都按顺序取出来放到字符串t中，分别给 pos 和字符串t排序，最后根据排序后的 pos 数组和字符串t来更新字符串s中对应位置的字母即可，参见代码如下：

解法一：

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        vector<vector<int>> g(n);
        vector<bool> visited(n);
        for (auto &pair : pairs) {
            g[pair[0]].push_back(pair[1]);
            g[pair[1]].push_back(pair[0]);
        }
        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            vector<int> pos;
            helper(g, i, pos, visited);
            string t;
            for (int idx : pos) t += s[idx];
            sort(pos.begin(), pos.end());
            sort(t.begin(), t.end());
            for (int j = 0; j < pos.size(); ++j) {
                s[pos[j]] = t[j];
            }
        }
        return s;
    }
    void helper(vector<vector<int>>& g, int i, vector<int>& pos, vector<bool>& visited) {
        visited[i] = true;
        pos.push_back(i);
        for (int next : g[i]) {
            if (visited[next]) continue;
            helper(g, next, pos, visited);
        }
    }
};

既然是结点连通问题，而且还可能分为不同的群组，那么就可以考虑是否可以用联合查找（又称并查集） Union Find 来做。LeetCode 上有很多可以使用该方法的题目，比如 Friend Circles 和 Redundant Connection 等等。这是一种给每个结点都初始化一个不同的 root 值，当两个结点相连时，将二者 root 值赋值为相同，最后对于同一个群组内的所有结点，它们的 root 值最后都是相同的。这里用一个大小为n的 root 数组，初始化均为 -1（也可以初始化为不同的值），然后就是更新 root 数组了，遍历每个 pair 对儿，通过 find 函数分别找出相连的两个结点的 root 值，若不相等，则将其赋值为相同。对于 find 函数，首先判断给定结点i的 root 值是否小于0，因为初始化为 -1，若仍是 -1，直接返回i（这样就省了将每个结点的 root 值都初始化为i的步骤）。若 root 值大于0了，则对 root[i] 再次调用 find 函数，将返回值更新 root[i]，更新的好处时减少了之后的调用递归的次数。更新完 root 数组之后，接下来就要将同一个群组的结点归类了，这里用一个二维数组g表示群组，遍历每个结点，调用 find 函数查找其群组号（即 root 值），将该结点加入该群组。然后就是遍历每个群组了，之后的逻辑就跟上面的 DFS 解法中的一样了，取出对应位置的字母，排序，再按顺序赋值回字符串s即可，参见代码如下：

解法二：

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        vector<int> root(n, -1);
        vector<vector<int>> g(n);
        for (auto &pair : pairs) {
            int x = find(root, pair[0]), y = find(root, pair[1]);
            if (x != y) {
                root[x] = y;
            }
        }
        for (int i = 0; i < n; ++i) {
            g[find(root, i)].push_back(i);
        }
        for (auto &a : g) {
            string t;
            for (int idx : a) t += s[idx];
            sort(t.begin(), t.end());
            for (int i = 0; i < a.size(); ++i) {
                s[a[i]] = t[i];
            }
        }
        return s;
    }
    int find(vector<int>& root, int i) {
        return root[i] < 0 ? i : root[i] = find(root, root[i]);
    }
};

Github 同步地址:

#1202

类似题目：

Minimize Hamming Distance After Swap Operations

参考资料：

https://leetcode.com/problems/smallest-string-with-swaps/

https://leetcode.com/problems/smallest-string-with-swaps/discuss/388257/C%2B%2B-with-picture-union-find

https://leetcode.com/problems/smallest-string-with-swaps/discuss/800257/C%2B%2B-DFS-solution-or-O(n-logn)

LeetCode All in One 题目讲解汇总(持续更新中...)