C++의 동형 문자열

두 개의 문자열 s와 t가 있다고 가정합니다. 동형인지 아닌지 확인해야 합니다. s의 문자를 t로 바꿀 수 있는 경우 두 문자열은 동형이라고 합니다.

모든 문자는 문자 순서를 유지하면서 다른 문자로 대체되어야 합니다. 두 캐릭터는 같은 캐릭터에 매핑될 수 없지만 한 캐릭터는 자신에게 매핑될 수 있습니다.

따라서 입력이 s ="egg", t ="add"와 같으면 e가 a에 매핑될 수 있고 g가 d에 매핑될 수 있으므로 출력은 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

크기가 256인 배열 arr를 정의하고 -1로 채웁니다.
크기가 256인 방문 배열을 정의하고 0으로 채웁니다.
크기가 256이고 0으로 채워지는 배열 Visit1을 정의합니다.
initialize i :=0의 경우, i <길이 s일 때 업데이트(i를 1만큼 증가), 수행 -
- 방문[s[i]]이 1과 같거나 방문1[t[i]]이 1과 같으면 -
  - arr[s[i]]가 t[i]와 같지 않은 경우 - 'a'의 ASCII, 다음 -
    - 거짓 반환
- 그렇지 않으면
  - 방문[s[i]] :=1
  - 방문1[t[i]] :=1
  - arr[s[i]] :=t[i] - 'a'의 ASCII
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"