Isomorphic Strings trong C++

Hai chuỗi s và t gọi là đồng cấu (isomorphic) nếu có thể thay thế ký tự trong s để được t, ánh xạ 1-1, bảo toàn thứ tự.

Ví dụ: s="egg", t="add" → true (e→a, g→d). s="foo", t="bar" → false (o ánh xạ tới cả a và r).

Giải thuật

Dùng 2 mảng/map kích thước 256 lưu ánh xạ s→t và t→s. Duyệt đồng thời, kiểm tra tính nhất quán.

Ví dụ triển khai C++

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

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> mapS(256, -1), mapT(256, -1);
        for (int i = 0; i < s.size(); i++) {
            char cs = s[i], ct = t[i];
            if (mapS[cs] != mapT[ct]) return false;
            mapS[cs] = mapT[ct] = i;
        }
        return true;
    }
};

int main() {
    Solution ob;
    cout << boolalpha << ob.isIsomorphic("sky", "fry"); // true
    return 0;
}

Đầu vào / Đầu ra

Input: "sky", "fry"
Output: true (1)