Chương trình kiểm tra có thể chuyển đổi xâu bằng thay thế ký tự trong C++

Mô tả bài toán

Cho hai xâu chữ thường s và t. Cho phép thực hiện phép toán: chọn một ký tự trong s và thay thế tất cả các lần xuất hiện của nó bằng một ký tự khác. Có thể làm nhiều lần. Kiểm tra xem có thể biến s thành t hay không.

Ví dụ: s = "eye", t = "pip" → True (thay 'e'→'p', 'y'→'i').

Giải thuật

1. Dùng hai bảng băm (map) m1 và m2 để lưu ánh xạ hai chiều.
2. Duyệt từng ký tự i:
   • Nếu s[i] đã có trong m1: kiểm tra m1[s[i]] == t[i], nếu không trả về false.
   • Ngược lại: gán m1[s[i]] = t[i].
3. Trả về true nếu không xung đột.

Ví dụ minh họa (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]) return false;
        } else {
            m1[s[i]] = t[i];
        }
        // Tương tự cho m2 nếu cần đảm bảo đơn ánh
    }
    return true;
}

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

Đầu vào

"eye","pip"

Đầu ra

1