C++에서 문자열을 동일하게 만들기 위한 최소 스왑

"x"와 "y" 문자로만 구성된 동일한 길이의 두 문자열 s1과 s2가 있다고 가정합니다. 우리의 임무는 이 두 문자열을 서로 동일하게 만드는 것입니다. 서로 다른 문자열에 속하는 두 문자를 교환할 수 있습니다. 즉 - 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 :=s1[i] 및 b :=s2[i]
- b와 같지 않으면
  - a ='x'이면 x1 증가, 그렇지 않으면 1만큼 y1 증가
  - b ='x'이면 x2 증가, 그렇지 않으면 y2 1 증가
(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"