Isomorphic Strings ใน C++

แนวคิด

สมมติว่ามีสตริง s และ t ให้ตรวจสอบว่ามัน isomorphic หรือไม่ สองสตริงเป็น isomorphic หากตัวอักษรใน s สามารถแทนที่เพื่อได้ t

ทุกครั้งที่ตัวอักษรปรากฏ ต้องแทนที่ด้วยอีกตัวอักษรหนึ่งพร้อมกันรักษาลำดับ ไม่มีสองตัวอักษร map ไปตัวเดียวกัน แต่ตัวอักษรอาจ map ไปตัวมันเองได้

เช่น ถ้าอินพุตคือ s = "egg", t = "add" ผลลัพธ์คือ true เพราะ e map ไป a และ g map ไป d

วิธีแก้:

• กำหนดอาร์เรย์ arr ขนาด 256 เติม -1
• กำหนดอาร์เรย์ visited ขนาด 256 เติม 0
• กำหนดอาร์เรย์ visited1 ขนาด 256 เติม 0
• วนลูป i := 0 ถึงความยาว s - 1:
  • ถ้า visited[s[i]] เท่ากับ 1 หรือ visited1[t[i]] เท่ากับ 1: ถ้า arr[s[i]] ไม่เท่ากับ t[i] - ASCII ของ 'a': คืนค่า false
  • มิฉะนั้น: visited[s[i]] := 1, visited1[t[i]] := 1, arr[s[i]] := t[i] - ASCII ของ 'a'
• คืนค่า true

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> arr(256, -1);
        vector<bool> visited(256, 0);
        vector<bool> visited1(256, 0);
        for (int i = 0; i < s.length(); i++) {
            if (visited[s[i]] == 1 || visited1[t[i]] == 1) {
                if (arr[s[i]] != t[i] - 'a') {
                    return false;
                }
            } else {
                visited[s[i]] = 1;
                visited1[t[i]] = 1;
                arr[s[i]] = t[i] - 'a';
            }
        }
        return true;
    }
};
main() {
    Solution ob;
    cout << (ob.isIsomorphic("sky","fry"));
}

อินพุต

"sky","fry"

เอาต์พุต

1