leetcode-1247

题目描述

思路及实现

看完题目及示例，能够很快想到要使两个字符串相等，那么两个字符串中的'x'和'y'的数量应该相等，所以可以先统计一下两者的数量，如果不同可以直接返回-1。
接下来从示例中寻找其他的情况，这边有两种思路：

1. 从示例4着手，这是我一开始的思路。用暴力方法来解决示例4，会发现需要6次才能够解决；那么4次怎么来的呢？那肯定是有选择性的交换，即优先选择更优方案；仔细观察交换，就能够发现其实有两种交换方案：第一种，s1 = 'x...x'和's2 = 'y...y'交换，这种情况下仅需一次交换；第二种，s1 = 'x...y'和s2 = 'y...x'交换，这种情况下需两次交换。那我们就更多地进行第一种交换就行了。
2. 总结数学规律，统计s1[i] = 'x', s2[i] = 'y'和s1[i] = 'y', s2[i] = 'x'的数量，计算结果。
   这其中的思路2涉及到的详细数学规律，可以跳转至官解观看。
   下面是思路1的代码：

   class Solution:
       def minimumSwap(self, s1: str, s2: str) -> int:
           if (s1.count('x') + s2.count('x')) % 2 != 0:  # 两字符串能够相同的前提是x或y的个数为偶数个
               return -1
           ans = 0
           n = len(s1)
           for index_1 in range(n):
               if s1[index_1] != s2[index_1]:  # 两个字符串中当前字符不相同
                   flag = False
                   for index_tmp in range(index_1 + 1, n):  # 贪心往后找和当前字符一样的情况
                       if s1[index_1] == s1[index_tmp] and s2[index_1] == s2[index_tmp]:  # 找到了的话交换次数+1，修改字符串
                           ans += 1
                           flag = True
                           s1 = s1[:index_tmp] + s2[index_1] + s1[index_tmp + 1:n]  # s1[index_tmp] = s2[index_1]
                           s2 = s2[:index_1] + s1[index_1] + s2[index_1 + 1:n]  # s2[index_1] = ch_1
                           break
                   if not flag:  # 没找到，就是需要交换两次的情况：'x...y', 'y...x'
                       for index_tmp in range(index_1 + 1, n):
                           if s1[index_1] == s2[index_tmp] and s2[index_1] == s1[index_tmp]:  # 交换次数+2，修改字符串
                               ans += 2
                               # s2[index_1] = ch_1, s2[index_tmp] = s1[index_tmp]
                               s2 = s2[:index_1] + s1[index_1] + s2[index_1 + 1:index_tmp] + s1[index_tmp] + s2[index_tmp + 1:n]
                               break
           return ans

   写得非常复杂，但是不涉及复杂数学规律，简单易懂（自己认为的），可以在此之上总结出数学规律。

---

希望本文章能够帮到您~