자바스크립트로 두 문자열이 동형(Isomorphic) 문자열인지 판별하는 방법

두 문자열 str1과 str2는 str1의 각 문자를 다른 문자로 치환했을 때 str2가 되는 경우, 동형(isomorphic) 문자열이라고 합니다.

예를 들어 다음과 같은 두 문자열을 살펴보겠습니다.

const str1 = 'abcde';
const str2 = 'eabdc';

str1의 'a'→'e', 'b'→'a', 'c'→'b', 'd'→'d', 'e'→'c'처럼 일관된 규칙으로 치환하면 str2를 만들 수 있으므로, 이 두 문자열은 동형 관계입니다.

문제 요구 사항

두 개의 문자열을 인수로 받아, 이 문자열들이 서로 동형인지 아닌지를 판별하는 자바스크립트 함수를 작성해야 합니다.

예제 코드

const str1 = 'abcde';
const str2 = 'eabdc';

const isIsomorphic = (str1 = '', str2 = '') => {
   if (str1.length !== str2.length) {
      return false;
   };
   for (let i = 0; i < str1.length; i++) {
      const a = str1.indexOf(str1[i]);
      const b = str2.indexOf(str2[i]);
      if (str2[a] !== str2[i] || str1[b] !== str1[i]) {
         return false;
      };
   };
   return true;
};
console.log(isIsomorphic(str1, str2));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true

코드 작동 원리

이 알고리즘의 핵심 로직은 다음과 같습니다.

1. 길이 검사

먼저 두 문자열의 길이가 다르면 치환으로 서로를 만들 수 없으므로 즉시 false를 반환합니다.

2. 첫 등장 위치 비교

각 인덱스 i에 대해 indexOf()를 사용해 현재 문자가 각 문자열에서 처음 등장한 위치를 구합니다. 만약 str1의 i번째 문자와 str2의 i번째 문자가 서로 다른 위치에서 처음 등장했다면, 두 문자열의 대응 관계가 깨진 것이므로 동형이 아닙니다.

3. 교차 검증

str2[a] !== str2[i] 조건은 str1 기준의 매핑을, str1[b] !== str1[i] 조건은 str2 기준의 역매핑을 확인합니다. 양방향 모두 일관성을 유지해야만 두 문자열은 동형입니다. 이렇게 하면 'egg'와 'add'는 동형이지만, 'foo'와 'bar'처럼 한 문자가 여러 문자에 대응되는 경우를 정확히 걸러낼 수 있습니다.

모든 문자에 대해 검사를 통과하면 최종적으로 true를 반환합니다.