Chuỗi đẳng hình trong C ++

Giả sử chúng ta có hai chuỗi s và t; chúng ta phải kiểm tra xem chúng có phải là đẳng cấu hay không. Hai chuỗi được cho là đẳng cấu nếu các ký tự trong s có thể được thay thế để lấy t.

Tất cả các lần xuất hiện của một ký tự phải được thay thế bằng một ký tự khác mà vẫn giữ nguyên thứ tự của các ký tự. Không có hai ký tự nào có thể ánh xạ đến cùng một ký tự nhưng một ký tự có thể ánh xạ với chính nó.

Vì vậy, nếu đầu vào giống như s ="egg", t ="add", thì đầu ra sẽ là true, vì e có thể ánh xạ tới a và g có thể ánh xạ tới d.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định arr mảng có kích thước 256 và điền bằng -1
Xác định một mảng được truy cập có kích thước 256 và điền bằng 0
Xác định một mảng đã thăm1 có kích thước 256 và điền bằng 0
để khởi tạo i:=0, khi i
- nếu đã truy cập [s [i]] giống với 1 hoặc đã truy cập1 [t [i]] giống với 1, thì -
  - nếu arr [s [i]] không bằng t [i] - ASCII của 'a' thì -
    - trả về false
- Nếu không
  - đã ghé thăm [s [i]]:=1
  - đã ghé thăm1 [t [i]]:=1
  - arr [s [i]]:=t [i] - ASCII của 'a'
trả về true

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"sky","fry"

Chuỗi đẳng hình trong C ++

Ví dụ

Đầu vào

Đầu ra