สมมติว่าเรามีสตริง A และ B สองสตริง สองสตริงนี้เป็น K-similar (โดยที่ K เป็นจำนวนเต็มที่ไม่ติดลบหนึ่งค่า) หากเราสามารถสลับตำแหน่งของตัวอักษรสองตัวใน A ตรง K ครั้งเพื่อให้สตริงที่ได้คือ B ดังนั้นเราจึงได้ สองแอนนาแกรม A และ B เราต้องหา K ที่เล็กที่สุดที่ A และ B เป็น K-similar
ดังนั้น หากอินพุตเป็น A ="abc", B ="bac" ผลลัพธ์จะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน swapp() ซึ่งจะใช้สตริง s, i, j,
-
x :=s[i], y :=s[j]
-
s[i] :=y, s[j] :=x
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ถ้า A เหมือนกับ B ดังนั้น:ให้คืนค่า 0
-
กำหนดการเยี่ยมชมหนึ่งชุด
-
ใส่ A เข้าไป
-
กำหนดหนึ่งคิว q แทรก A ลงใน q
-
สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -
-
sz :=ขนาดของ q
-
ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz ลง 1 ในการวนซ้ำแต่ละครั้ง ให้ทำ -
-
curr :=องค์ประกอบแรกของ q
-
ลบองค์ประกอบออกจาก q
-
ผม :=0
-
ในขณะที่ (i <ขนาดของ curr และ curr[i] เท่ากับ B[i]) ทำ −
-
(เพิ่ม i ขึ้น 1)
-
-
สำหรับการเริ่มต้น j :=i + 1 เมื่อ j <ขนาดของ curr ให้อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -
-
ถ้า curr[i] เหมือนกับ curr[j] แล้ว −
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
ถ้า curr[j] ไม่เท่ากับ B[i] แล้ว −
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
ถ้า curr[j] เหมือนกับ B[j] แล้ว −
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
swapp(curr, i, j)
-
ถ้าสกุลเงินเหมือนกับ B แล้ว −
-
กลับเลเวล
-
-
หากไม่นับจำนวนครั้งที่เข้าเยี่ยมชม −
-
ใส่เคอร์เนลเข้าที่เข้าชมแล้ว
-
ใส่เคอร์เนลลงใน q
-
-
swapp(curr, i, j)
-
-
-
-
กลับ -1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kSimilarity(string A, string B) {
if (A == B)
return 0;
unordered_set<string> visited;
visited.insert(A);
queue<string> q;
q.push(A);
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
string curr = q.front();
q.pop();
int i = 0;
while (i < curr.size() && curr[i] == B[i])
i++;
for (int j = i + 1; j < curr.size(); j++) {
if (curr[i] == curr[j])
continue;
if (curr[j] != B[i])
continue;
if (curr[j] == B[j])
continue;
swapp(curr, i, j);
if (curr == B)
return lvl;
if (!visited.count(curr)) {
visited.insert(curr);
q.push(curr);
}
swapp(curr, i, j);
}
}
}
return -1;
}
void swapp(string &s, int i, int j) {
char x = s[i];
char y = s[j];
s[i] = y;
s[j] = x;
}
};
main(){
Solution ob;
cout << (ob.kSimilarity("abc", "bac"));
} อินพุต
"abc", "bac"
ผลลัพธ์
1
