C#으로 두 문자열이 동형(Isomorphic)인지 확인하는 방법

두 문자열 X와 Y에서 X의 각 문자가 다른 문자로 치환되어 Y가 될 수 있고, 그 반대도 가능하다면 이 두 문자열을 동형(isomorphic)이라고 합니다. 예를 들어 ACAB와 XCXY를 살펴보겠습니다. 모든 문자 치환 과정에서는 문자의 순서가 유지되어야 하며, 서로 다른 두 문자가 같은 문자에 매핑될 수는 없습니다. 단, 한 문자가 자기 자신에게 매핑되는 것은 허용됩니다.

예제 1

입력 − s = "egg", t = "add"

출력 − true

예제 2

입력 − s = "foo", t = "bar"

출력 − false

위 예제에서 'egg'와 'add'는 e→a, g→d로 일관되게 매핑되므로 동형입니다. 반면 'foo'와 'bar'는 f→b로 매핑된 상태에서 o가 r과 a라는 서로 다른 문자에 매핑되어야 하므로 동형이 아닙니다.

시간 복잡도

O(N) — 문자열의 길이에 비례하여 한 번만 순회합니다.

공간 복재도

O(N) — 각 문자의 마지막 등장 위치를 저장하기 위한 배열을 사용합니다.

구현 코드

public class Arrays {
    public bool IsStringIsomorphic(string s, string t) {
        if (s == null || t == null) {
            return false;
        }
        int[] chars1 = new int[128];
        int[] chars2 = new int[128];
        for (int i = 0; i < s.Length; i++) {
            if (chars1[s[i]] != chars2[t[i]]) {
                return false;
            } else {
                chars1[s[i]] = i + 1;
                chars2[t[i]] = i + 1;
            }
        }
        return true;
    }
}

static void Main(string[] args) {
    Console.WriteLine(s.IsStringIsomorphic("add", "egg"));
}

실행 결과

True

코드 설명

이 알고리즘은 길이가 128인 정수 배열 두 개(chars1, chars2)를 사용합니다. 각 배열은 해당 문자가 마지막으로 등장한 인덱스를 기록합니다. 두 문자열을 동시에 순회하면서 s의 문자와 t의 문자가 기록해 둔 마지막 위치가 서로 다르면, 즉 하나의 문자가 여러 문자에 매핑되려 하면 false를 반환합니다. 위치가 같다면 두 배열 모두 현재 인덱스(i + 1)로 갱신합니다. 모든 문자를 검사한 후 문제가 없으면 true를 반환하여 두 문자열이 동형임을 확인할 수 있습니다.