题目大意：
交换字符使得字符串相同
有两个长度相同的字符串 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1247
解题思路分析：
看了题目之后，并没有想到应该套用什么算法来解题，因此只能寻找规律，看看都有哪些情况。
由于题目给出的2个字符串只包含2种字符x和y。首先要想到，如果当前index下两个字符串对应的字符相同，那么这一位是不需要修改的。反之，同Index下s1和s2相对应的字符不同，我们需要作出替换操作，替换时，我们只能找另一组不匹配的index来做替换操作，因此我们可以得出第一个结论，当不匹配的index数为奇数时，无论如何我们是无法完成替换操作的，应该返回-1。比如：
s1=xxy; s2=yxy;
再考虑我们该如何替换字符来使得两个字符串当前位的字符相同。比如，s1的当前位是x，s2的当前位为y，替换s1和替换s2的效果相同，也就是说，要不将s1的x变为y，要不将s2的y变为x，不过需要注意的是，用来替换的字符必须从另一个字符串中寻找，寻找时应该遵循如下原则：
- 用来替换字符所在的index不能与当前位相同。解释：当前位置的两个字符不同，如果用当前位的另一个字符与自身替换，替换后两个字符还是不同，只不过改变了一下所属字符串而已。
- 用来替换字符不能与当前字符相同。解释：替换来一个相同的字符等于什么都没做啊！
有了上面两个原则，解题就变得简单一些了，举个例子：
s1 = xxx; s2 = yxy;
我们发现，第0位的两个字符不同，我们尝试将s1的x替换为y，这时应该在s2中找到不是第0位的不匹配index，并且s2在该index的字符不是x，因此index为2的y是最佳目标，替换后：
s1 = yxx; s2 = yxx;
第0位都变成了y，同时第2为也都变为了x，我们通过一次变换，一次性修改好了2位！
思考到这里我以为都想通了，但还是落下了一个case，比如下面这种：
s1 = xy; s2 = yx;
如果利用我们上面的2条原则来替换的话，上面这个例子无法满足替换条件，比如s1中的x，我们想要将其修改为y，那么要在s2中找到不在第0位且为y的元素，显然没有。这时应该怎么处理？题目的例子也给出了这种情况，显然我们需要2次交换才能达到目的。经过反复的思考，我肯定这种case在两个字符串中最多只会出现一次，比如：
s1 = xyxy; s2 = yxyx; 或者 s1 = xyyy; s2 = yxxx;
只要还存在其他的不匹配index，我们都能利用上面的两条原则将其化解，留下的特殊情况最多只有一组。(这里属于贪心算法？)
这样问题就变为，首先利用2条原则将可变的部分改变，如果剩下特殊情况，结果再加2即可。
解题思路大致如下：
- 先循环一遍字符串，记录下哪些位是不匹配的，并记录下不匹配位置的总数。
- 如果不匹配的个数为奇数，返回-1。
- 再循环一遍字符串，遇到匹配的位置跳过。如果当前位置不匹配的话，从当前位置向后循环，找到下一个不匹配的位置，并且另外一个字符串中那个位置的字符与当前位置本字符串的字符不同，代表可以替换，结果加1，同时将下一个不匹配位置的标志更改为匹配。此外还要将不匹配位置的总数减去2。
- 循环结束后，如果不匹配位置为2，说明有上述的特殊情况存在，此时结果还需再加上2。
实现代码：
public int minimumSwap(String s1, String s2) {
// 统计哪些位不匹配
boolean[] invalid = new boolean[s1.length()];
int errorCount=0; // 统计不匹配位置的个数
for(int i=0;i<s1.length();i++){ // 循环字符串
// 如果当前位不同
if(s1.charAt(i) != s2.charAt(i)){
invalid[i]=true; // 当前位设为不匹配
errorCount++; // 不匹配个数加1
}
}
// 如果不匹配个数为奇数，返回-1。
if(errorCount % 2==1) return -1;
int res=0; // 返回结果
for(int i=0;i<s1.length();i++){ // 循环字符串
if(!invalid[i]) continue; // 当前位匹配，略过。
for(int j=i+1;j<s1.length();j++){ // 找到下一个不匹配
// 如果不匹配并且另一个字符串的字符与当前字符串字符不同
if(invalid[j] && s1.charAt(i) != s2.charAt(j)){
res++; // 结果加一
invalid[j]=false; // 下一个不匹配更新为匹配
errorCount-=2; // 不匹配个数减2
break;
}
}
}
// 如果还存在不匹配个数，说明存在特殊情况，结果加2
if(errorCount==2) res+=2;
return res;
} 本解法运行时间为1ms。
Runtime: 1 ms, faster than 54.68% of Java online submissions for Minimum Swaps to Make Strings Equal.
Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Minimum Swaps to Make Strings Equal.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1247-minimum-swaps-to-make-strings-equal-解题思路分析/