原文链接: https://leetcode-cn.com/problems/minimum-swaps-to-make-strings-equal

英文原文

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'.

中文题目

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

 

示例 1：

输入：s1 = "xx", s2 = "yy"
输出：1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

输入：s1 = "xy", s2 = "yx"
输出：2
解释：
交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

输入：s1 = "xx", s2 = "xy"
输出：-1

示例 4：

输入：s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
输出：4

 

提示：

• 1 <= s1.length, s2.length <= 1000
• s1, s2 只包含 'x' 或 'y'。

通过代码

高赞题解

1. 题目分析

• 第一步：普遍规律
  由于要求交换次数尽量少，故：
  • 本来相同位置就有相同的字符，不需要交换。
  • 本来相同位置字符不同，需要交换。交换为两组字符交换，本质上只有两种情形：
    
    (a) 2组相同(2组xy或2组yx，等价于示例1)：

      此时，`s1[0]`与`s2[1]`交换即可，需要进行$1$次交换
    

    (b) 2组不同(1组xy，1组yx，等价于示例2)：

      此时，将`s1[0]`与`s2[0]`交换后与a)相同，需要进行$2$次交换
    

    
    综上所述，我们可以得出如下结论：
    • xy与yx的组数之和必须为偶数，否则返回-1(两两交换)
    • 优先进行(a)类交换，剩余的进行(b)类交换(贪心算法)
• 第二步：得出结论
  由于匹配是两两进行，因此，在确定有$M$对xy，$N$对yx，且$M+N$为偶数后：
  • 若$M$为偶数，则$N$也为偶数，则全部为(a)类交换。总匹配数为：
    $$\frac{M + N}{2}$$
  • 若$M$为奇数，则$N$也为奇数，则各拿一组进行(b)类交换，其余(a)类交换。总匹配数为：
    $$\frac{M - 1}{2} + \frac{N - 1}{2} + 2 = \frac{M + N}{2} + 1$$
  • 两者均可写作：
    $$\frac{M + 1}{2} + \frac{N + 1}{2}$$

2. Coding

public int minimumSwap(String s1, String s2) {
    int len = s1.length(), xy = 0, yx = 0;
    for(int i = 0; i < len; i ++) {
        if(s1.charAt(i) == s2.charAt(i)) {
            continue;
        }
        else if(s1.charAt(i) == 120) {
            xy ++;
        }
        else {
            yx ++;
        }
    }
    return ((xy + yx) & 1) == 1 ? -1 : (xy + 1) / 2 + (yx + 1) / 2;
}

时间复杂度：$O(n)$，空间复杂度：$O(1)$

注1：代码中判断是否为奇数的方法经常会用到，也可以将其抽取为一个方法进行调用：

private boolean isOdd(int t) {
    return (t & 1) == 1;
}

注2：上面的代码执行的结果为1ms，使用toCharArray()方法代替charAt()方法，可以实现0ms

public int minimumSwap(String s1, String s2) {
    int len = s1.length(), xy = 0, yx = 0;
    char[] cs1 = s1.toCharArray();
    char[] cs2 = s2.toCharArray();
    for(int i = 0; i < len; i ++) {
        if(cs1[i] == cs2[i]) {
            continue;
        }
        else if(cs1[i] == 120) {
            xy ++;
        }
        else {
            yx ++;
        }
    }
    return ((xy + yx) & 1) == 1 ? -1 : (xy + 1) / 2 + (yx + 1) / 2;
}

此时，时间复杂度：$O(n)$，空间复杂度：$O(n)$

3. 执行结果

• 方法一
  
• 方法二
  

统计信息

通过次数	提交次数	AC比率
9325	15031	62.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言