使C ++中的字符串相等的最小交换

假设我们有两个长度相等的字符串s1和s2，仅由字母“ x”和“ y”组成。我们的任务是使这两个字符串彼此相等。我们可以交换属于不同字符串的任意两个字符，这意味着-交换s1 [i]和s2 [j]。我们必须找到使s1和s2相等所需的最小交换数，如果不可能，则返回-1。因此，如果字符串是s1 =“ xy”而s2 =“ yx”，则输出将为2。如果我们交换s1 [0]和s2 [0]，则s1 =“ yy”，s2 =“ xx”。然后交换s1 [0]和s2 [1]，s1 =“ xy”，s2 =“ xy”。

为了解决这个问题，我们将遵循以下步骤-

• 将x1，x2，y1和y2设置为0

• 对于范围从0到s1的i

• 如果a ='x'，则将x1加1，否则将y1加1

• 如果b ='x'然后增加x2，否则将y2增加1

• a：= s1 [i]和b：= s2 [i]

• 如果a与b不同，则

• 如果（x1 + x2）为奇数或（y1 + y2）为奇数，则返回-1

• 返回x1 / 2 + y1 / 2 +（x1 mod 2）* 2

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumSwap(string s1, string s2) {
      int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
      for(int i = 0; i < s1.size(); i++){
         char a = s1[i];
         char b = s2[i];
         if(a != b){
            if(a == 'x')x1++;
            else y1++;
            if(b == 'x')x2++;
            else y2++;
         }
      }
      if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
      return x1/2 + y1/2 + (x1 % 2) * 2;
   }
};
main(){
   Solution ob;
   cout <<ob.minimumSwap("xy", "yx");
}

输入项

"xy"
"yx"

输出结果

2