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"

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 CirclesRedundant 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation