[LeetCode] 1247. Minimum Swaps to Make Strings Equal #1247

grandyang · 2019-05-30T16:33:41Z

You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2:

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

Example 4:

Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4

Constraints:

1 <= s1.length, s2.length <= 1000
s1, s2 only contain 'x' or 'y'.

这道题说是给了只有包含x和y两种字母的字符串 s1 和 s2，现在为了使得二者变为相等，可以任意交换 s1 和 s2 中的两个字符，现在问最小交换多少次可以使得二者相等，若无法变为相等，返回 -1。读完题目之后，接下来就是要分析例子了，这道题的例子给的非常好，关键的解题思路都隐藏在了例子当中。首先来看第一个例子，当对应位置都是x和y的时候，只要对称交换一下，就可以都变成 yx，这种情况只要一次替换。而对于例子2来说，对应位置互为相反，一个是 x->y，另一个是 y->x，这种情况需要两次替换，先换成对应位置相同的情况，也就是例子1的情况，然后再替换一次，变为相等。

对于例子3来说，由于两组映射既不相等，也不对称，所以无论如何替换，都无法变为相等。例子4比较长，可以先移除相同位置的相同字符后，就变成了 xyxyyx 和 yxyxxy，此时的策略是，能用例子1的替换方法时就尽量先用，因为其只需一次替换，实在不行了再用例子2的替换方式。当然这取决于映射之间的关系，因为这里对应的位置的映射只有两种：x->y 和 y->x，可以分别统计个数，这里的 x->y 映射有3个，y->x 映射也有3个。前面说了，应该先凑例子1的模式，则分别取出两个 x->y 和两个 y->x 组成例子1的模式，总共消耗两次替换即可，剩下了一个 x->y 和一个 y->x 映射，正好就是例子2的情况，需要两次替换，总共需要4次替换操作。

分析到这里，题目也就没啥难度了，博主最开始写的时候，没有注意看题目说只有x和y两种字母，以为还有其他字母，所以写了一个可以通用的解法，将两个字母中间加个下划线，当作 HashMap 的 key，映射到其出现的次数，注意要先跳过相同的字母。映射数统计好了之后，就用前面分析的策略，先凑例子1的情况，把每个映射次数除以2，就能凑出的例子1情况的次数，直接加到结果 res 中，若还有剩余，则将个数加到另一个变量 cnt 中。最终 cnt 中的映射都是不同的，只能组成例子2的情况，若其为奇数，则说明有落单的，无法替换了，直接返回 -1，否则的话就返回 res+cnt 即可，参见代码如下：

解法一：

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int res = 0, n = s1.size(), cnt = 0;
        unordered_map<string, int> m;
        for (int i = 0; i < n; ++i) {
            if (s1[i] == s2[i]) continue;
            ++m[string(1, s1[i]) + "_" + string(1, s2[i])];
        }
        for (auto &a : m) {
            res += a.second / 2;
            cnt += a.second % 2;
        }
        return cnt % 2 != 0 ? -1 : res + cnt;
    }
};

由于这道题只有x和y两个字母，所以只需要统计 x->y 和 y->x 两种映射即可，用两个变量 xy 和 yx 来表示即可，不需要使用 HashMap。统计好了之后，判断若 xy 和 yx 不同奇偶的话，说明一定有落单了，返回 -1，否则返回 xy/2 + yx/2 + (xy%2) * 2。这个表达式也不难理解，xy/2 + yx/2 就是例子1的情况所需要的替换次数，然后 xy % 2 可以知道 x->y 映射的奇偶，只有其是奇数的时候，才会有剩余，跟最后剩下的一个 y->x 映射组成例子2的情况即可，参见代码如下：

解法二：

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int res = 0, n = s1.size(), xy = 0, yx = 0;
        for (int i = 0; i < n; ++i) {
            if (s1[i] == 'x' && s2[i] == 'y') ++xy;
            else if (s1[i] == 'y' && s2[i] == 'x') ++yx;
        }
        return (xy % 2 != yx % 2) ? -1 : (xy / 2 + yx / 2 + (xy % 2) * 2);
    }
};

Github 同步地址:

#1247

类似题目：

Determine if Two Strings Are Close

参考资料：

https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/

https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/discuss/419691/C%2B%2B-simple-solution

https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/discuss/419874/Simply-Simple-Python-Solution-with-detailed-explanation

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

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|