สมมติว่าเรามีสตริงสองสตริง 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
- สำหรับ i ในช่วง 0 ถึงขนาด s1
- a :=s1[i] และ b :=s2[i]
- ถ้า a ไม่เหมือนกับ b แล้ว
- ถ้า a ='x' ให้เพิ่ม x1 ไม่เช่นนั้นให้เพิ่ม y1 ขึ้น 1
- ถ้า 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"
ผลลัพธ์
2
