จำนวนการดำเนินการน้อยที่สุดเพื่อทำให้สตริงสองตัวเท่ากันด้วย C++

ข้อความโจทย์

กำหนดสตริงสองตัว str1 และ str2 ทั้งสองตัวมีตัวอักษร 'a' และ 'b' ทั้งสองสตริงมีความยาวเท่ากัน มี _ (ช่องว่าง) อยู่ในทั้งสองสตริง งานคือแปลงสตริงแรกเป็นสตริงที่สอง โดยทำจำนวนการดำเนินการน้อยที่สุดของดังต่อไปนี้ -

• ถ้า _ อยู่ตำแหน่ง i แล้ว _ สามารถสลับกับตัวอักษรตำแหน่ง i+1 หรือ i-1
• ถ้าตัวอักษรตำแหน่ง i+1 และ i+2 ต่างกัน _ สามารถสลับกับตัวอักษรตำแหน่ง i+1 หรือ i+2
• เช่นเดียวกัน ถ้าตัวอักษรตำแหน่ง i-1 และ i-2 ต่างกัน _ สามารถสลับกับตัวอักษรตำแหน่ง i-1 หรือ i-2

ถ้า str1 = "aba_a" และ str2 = "_baaa" แล้วเราต้องการ 2 การเคลื่อนที่เพื่อแปลง str1 เป็น str2 -

1. str1 = "ab_aa" (สลับ str1[2] กับ str1[3])
2. str2 = "_baaa" (สลับ str1[0] กับ str1[2])

อัลกอริทึม

1. ใช้ Breadth First Search (BFS) แบบง่ายบนสตริง และสมาชิกของคิวที่ใช้สำหรับ BFS จะมีคู่ str, pos โดยที่ pos คือตำแหน่งของ _ ในสตริง str
2. รักษาแมปชื่อ 'vis' ซึ่งจะเก็บสตริงเป็นกุญแจ และจำนวนการเคลื่อนที่ขั้นต่ำเพื่อไปถึงสตริงนั้นเป็นค่า
3. สำหรับสตริง str ทุกตัวจากคิว สร้างสตริงใหม่ tmp ตามเงื่อนไข 4 ข้อที่กำหนด และอัปเดตแมป vis เป็น vis[tmp] = vis[str] + 1
4. ทำซ้ำขั้นตอนข้างต้นจนกว่าคิวจะว่าง หรือสตริงที่ต้องการถูกสร้างขึ้น คือ tmp == B
5. ถ้าสตริงที่ต้องการถูกสร้างแล้ว ให้คืนค่า vis[str] + 1 ซึ่งเป็นจำนวนการดำเนินการขั้นต่ำที่ต้องใช้เพื่อเปลี่ยน A เป็น B

ตัวอย่างโค้ด

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;

int transformString(string str, string f) {
    unordered_map<string, int> vis;
    int n;
    n = str.length();
    int pos = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '_') {
            pos = i;
            break;
        }
    }
    queue<pair<string, int> > q;
    q.push({ str, pos });
    vis[str] = 0;
    while (!q.empty()) {
        string ss = q.front().first;
        int pp = q.front().second;
        int dist = vis[ss];
        q.pop();
        if (pp > 0) {
            swap(ss[pp], ss[pp - 1]);
            if (!vis.count(ss)) {
                if (ss == f) {
                    return dist + 1;
                    break;
                }
                vis[ss] = dist + 1;
                q.push({ ss, pp - 1 });
            }
            swap(ss[pp], ss[pp - 1]);
        }
        if (pp < n - 1) {
            swap(ss[pp], ss[pp + 1]);
            if (!vis.count(ss)) {
                if (ss == f) {
                    return dist + 1;
                    break;
                }
                vis[ss] = dist + 1;
                q.push({ ss, pp + 1 });
            }
            swap(ss[pp], ss[pp + 1]);
        }
        if (pp > 1 && ss[pp - 1] != ss[pp - 2]) {
            swap(ss[pp], ss[pp - 2]);
            if (!vis.count(ss)) {
                if (ss == f) {
                    return dist + 1;
                    break;
                }
                vis[ss] = dist + 1;
                q.push({ ss, pp - 2 });
            }
            swap(ss[pp], ss[pp - 2]);
        }
        if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) {
            swap(ss[pp], ss[pp + 2]);
            if (!vis.count(ss)) {
                if (ss == f) {
                    return dist + 1;
                    break;
                }
                vis[ss] = dist + 1;
                q.push({ ss, pp + 2 });
            }
            swap(ss[pp], ss[pp + 2]);
        }
    }
    return 0;
}

int main() {
    string str1 = "aba_a";
    string str2 = "_baaa";
    cout << "Minimum required moves: " << transformString(str1, str2) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required moves: 2