Medium

题目描述

给你两个长度相等的字符串 s1 和 s2，它们只包含字母 'x' 和 'y'。你的任务是使这两个字符串相等。你可以交换任意两个属于不同字符串的字符，也就是说：交换 s1[i] 和 s2[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

提示：

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

解题思路

解题思路

这道题的关键在于分析不匹配位置的模式。首先忽略所有已经匹配的位置（s1[i] == s2[i]），只关注不匹配的位置。

对于不匹配的位置，只有两种情况：

  1. s1[i] = 'x', s2[i] = 'y'
  2. s1[i] = 'y', s2[i] = 'x'

设第一种情况有 xy 对，第二种情况有 yx 对。

核心观察：

  • 如果总的不匹配位置数量为奇数，那么不可能使两个字符串相等，返回 -1
  • 对于两个 xy 对，可以用 1 次交换解决：交换两个 xy 对中的任意一个 x 和任意一个 y
  • 对于两个 yx 对，可以用 1 次交换解决：交换两个 yx 对中的任意一个 y 和任意一个 x
  • 对于一个 xy 对和一个 yx 对，需要 2 次交换解决

贪心策略：

  1. 优先配对相同类型：xy + xy = 1 次交换，yx + yx = 1 次交换
  2. 剩余的不同类型配对：xy + yx = 2 次交换

最终答案：xy/2 + yx/2 + (xy%2)*2

代码实现

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        
        for (int i = 0; i < s1.length(); i++) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                xy++;
            } else if (s1[i] == 'y' && s2[i] == 'x') {
                yx++;
            }
        }
        
        // 如果不匹配的总数为奇数，不可能平衡
        if ((xy + yx) % 2 == 1) {
            return -1;
        }
        
        // xy/2 对xy需要xy/2次交换
        // yx/2 对yx需要yx/2次交换  
        // 剩余的(xy%2)个xy和(yx%2)个yx需要2次交换
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
};

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy = 0  # s1[i]='x', s2[i]='y' 的数量
        yx = 0  # s1[i]='y', s2[i]='x' 的数量
        
        for i in range(len(s1)):
            if s1[i] == 'x' and s2[i] == 'y':
                xy += 1
            elif s1[i] == 'y' and s2[i] == 'x':
                yx += 1
        
        # 如果不匹配的总数为奇数，不可能平衡
        if (xy + yx) % 2 == 1:
            return -1
        
        # xy//2 对xy需要xy//2次交换
        # yx//2 对yx需要yx//2次交换
        # 剩余的(xy%2)个xy和(yx%2)个yx需要2次交换
        return xy // 2 + yx // 2 + (xy % 2) * 2

public class Solution {
    public int MinimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        
        for (int i = 0; i < s1.Length; i++) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                xy++;
            } else if (s1[i] == 'y' && s2[i] == 'x') {
                yx++;
            }
        }
        
        // 如果不匹配的总数为奇数，不可能平衡
        if ((xy + yx) % 2 == 1) {
            return -1;
        }
        
        // xy/2 对xy需要xy/2次交换
        // yx/2 对yx需要yx/2次交换
        // 剩余的(xy%2)个xy和(yx%2)个yx需要2次交换
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
}

var minimumSwap = function(s1, s2) {
    let xy = 0, yx = 0;
    
    for (let i = 0; i < s1.length; i++) {
        if (s1[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目