สตริง Isomorphic ใน C ++

สมมติว่าเรามีสองสตริง s และ t; เราต้องตรวจสอบก่อนว่าเป็นไอโซมอร์ฟิคหรือไม่ สตริงสองสายเรียกว่า isomorphic หากอักขระใน s สามารถแทนที่เพื่อรับ t ได้

ทุกรายการของอักขระต้องถูกแทนที่ด้วยอักขระอื่นในขณะที่รักษาลำดับของอักขระ ห้ามอักขระสองตัวจับคู่กับอักขระตัวเดียวกัน แต่อักขระหนึ่งตัวอาจจับคู่กับตัวมันเอง

ดังนั้น หากอินพุตเป็นเหมือน s ="egg", t ="add" ผลลัพธ์จะเป็นจริง เนื่องจาก e สามารถจับคู่กับ a และ g สามารถจับคู่กับ d ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ arr ขนาด 256 และเติมด้วย -1

• กำหนดอาร์เรย์ที่เข้าชมขนาด 256 และเติมด้วย 0

• กำหนดอาร์เรย์ที่เข้าชม 1 ขนาด 256 และเติมด้วย 0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า visit[s[i]] เหมือนกับ 1 หรือ visit1[t[i]] เหมือนกับ 1 แล้ว −

    • ถ้า arr[s[i]] ไม่เท่ากับ t[i] - ASCII ของ 'a' ดังนั้น −

      • คืนค่าเท็จ

  • มิฉะนั้น

    • เยี่ยมชม[s[i]] :=1

    • เยี่ยมชม1[t[i]] :=1

    • arr[s[i]] :=t[i] - ASCII ของ 'a'

• คืนความจริง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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