Loading... ## 题目 有两个长度相同的字符串 `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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用,请我喝杯咖啡吧。