โปรแกรมตรวจสอบว่าแทนที่ตัวอักษรได้เป็นสตริงเป้าหมายหรือไม่ใน C++

ให้สตริง s และ t ตัวพิมพ์เล็ก ทำการดำเนินการ: เลือกตัวอักษรใน s แล้วแทนที่ทุกครั้งที่ปรากฏด้วยตัวอักษรอื่น ทำซ้ำได้ไม่จำกัดครั้ง ต้องการทราบว่า s สามารถกลายเป็น t ได้หรือไม่

ตัวอย่าง: s = "eye", t = "pip" → True (แทนที่ 'e'→'p', 'y'→'i')

ขั้นตอนการแก้ปัญหา

1. สร้าง Map m1 (char → char)
2. วนลูป i = 0 ถึง n-1:
   • ถ้า s[i] อยู่ใน m1 แล้ว:
     • ถ้า m1[s[i]] == t[i] → ต่อไป
     • มิฉะนั้น → คืนค่า false
   • มิฉะนั้น: m1[s[i]] = t[i]
3. คืนค่า true

หมายเหตุ: ต้องตรวจสอบการแมปแบบ 1-1 (bijection) จึงควรมี m2 สำหรับทิศทางกลับด้วย

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

#include <bits/stdc++.h>
using namespace std;

bool solve(string s, string t) {
    unordered_map<char, char> m1, m2;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (m1.count(s[i])) {
            if (m1[s[i]] == t[i]) continue;
            return false;
        } else {
            m1[s[i]] = t[i];
        }
        if (m2.count(t[i])) {
            if (m2[t[i]] == s[i]) continue;
            return false;
        } else {
            m2[t[i]] = s[i];
        }
    }
    return true;
}

int main() {
    string s = "eye", t = "pip";
    cout << solve(s, t);
    return 0;
}

อินพุต

"eye", "pip"

เอาต์พุต

1