leetcode 1247. 交换字符使得字符串相同

zhaojun

2023 年 02 月 26 日

1276 次浏览

暂无评论

749字数

默认分类

## 题目

有两个长度相同的字符串 `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 即可。

然后从头到尾判断每个字符的情况，有三种可能：

1. `s1[i] == s2[i]` 两个字符相等，可直接跳过，无需交换
2. `s1[i] == 'x', s2[i] == 'y'`
3. `s1[i] == 'y', s2[i] == 'x'`

对于以下几种情况，只需要交换一次即可，即斜对角交换：
```bash
x   x  ＝  y   x      y   y  =  x   y
 ↖                     ↖         
   ↘                     ↘        
y   y      y   x      x   x     x   y
```

对于以下情况，需要两次交换，即先上下，在斜对角交换：
```bash
x   y   =    y   y  =   x   y
↑             ↖         
↓               ↘
y   x        x   x      x   y
```

根据上面的规律，可以得出，每两个 xy 可以当成 1 次，每两个 yx 也可以当成交换 1 次。
剩下不成对的，则就是需要交换两次的了。xy 和 yx 组成一对当成需要交换 2 次。

这样的话，也可以得出，如果 xy + yx 不是偶数的话，他是不可能凑成对来交换的，所以这种情况也可以直接返回 -1

## 代码
```java
class Solution {
    public int minimumSwap(String s1, String s2) {
        int len = s1.length();
        if (s2.length() != len) return -1;
        int xy = 0, yx = 0;
        for (int i = 0; i < len; i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                continue;
            }

if (s1.charAt(i) > s2.charAt(i)) {
                yx++;
            } else {
                xy++;
            }
        }

if ((xy + yx) % 2 != 0) return -1;
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
}
```

最后修改：2023 年 02 月 26 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 1247. 交换字符使得字符串相同

zhaojun • 2023 年 02 月 26 日

leetcode 1247. 交换字符使得字符串相同

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

Shiro 学习 03 - Realm

Percona XtraDB Cluster 集群搭建

Percona Monitoring and Management (PMM) 安装与配置

leetcode 257 二叉树的所有路径

MySQL 学习 01 - 连接

leetcode 1247. 交换字符使得字符串相同

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 1247. 交换字符使得字符串相同

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款