1247. 交换字符使得字符串相同
题目描述
有两个长度相同的字符串 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 的条件：xy 和 yx（即s1[i] + s2[i] 的组合） 的次数不为偶数，即 （xy+yx） % 2 == 1， 代码里我用数组 dif 保存 xy 和 yx 的次数，dif[0] 保存 xy ，dif[1] 保存 yx。
-
求解最小交换次数， 使用贪心算法，如果 s1[i] == s2[i] ，那么不需要交换；如果 s1[i] 和 s2[i] 不相同，有两种情况：xy 和 yx 。观察示例 1 和示例 2 ，交换字符也有两种情况：
- 进行一次交换，可以使 xy 或 yx 的次数减少 2；
- 进行两次交换，可以使 xy 和 yx 的次数各减少 1；
-
为了使得交换次数最少，从以下情况来考虑：
- 显然第一次交换效率更高，因此应尽可能使用第一种方式；
- 如果 xy 或 yx 还没有等于 0，那么需要使用第二种方式；
- 当 xy 和 yx 的次数都为 1 时（即示例2），没办法使用第一种方式，此时也是选择第二种方式。
-
最后可以总结为，最小出现次数可以总结为：
ceil((float)dif[0] / 2) + ceil((float)dif[1] / 2)。
收获
- 对于 -1 的判断， 我一开始是统计了 x 和 y 的出现次数， 倘若其中 x 或 y 的出现次数为奇数， 那么就不能交换；看了题解，可以直接简化为 xy + yx 为奇数，那么就不能交换。
算法情况
- 时间复杂度：O（n），其中 n 为 s1 或 s2 的长度；
- 空间复杂度：O（C），其中 C 为 2 。
代码
class Solution {
public:int minimumSwap(string s1, string s2) {int ans = 0;int len = s1.size();vector<int> dif(2);for(int i=0; i<len; ++i){if(s1[i] == 'x' && s2[i] == 'y') dif[0] ++;if(s1[i] == 'y' && s2[i] == 'x') dif[1] ++; }if((dif[0] + dif[1]) % 2 != 0) return -1;ans = ceil((float)dif[0] / 2) + ceil((float)dif[1] / 2);return ans;}
};
