Isomorphic Strings

Q: 동형 문자열(Isomorphic Strings)의 시간 복잡도는 무엇인가요?

두 맵을 사용하는 풀이에서는 각 위치를 한 번씩만 읽으므로 실행 시간은 O(n) 입니다. 맵에는 가능한 문자(영문자와 숫자 62개)마다 항목이 최대 하나씩 저장되므로 추가 공간은 O(1) 입니다. 모든 위치 쌍을 비교하면 O(n²) 의 시간이 걸립니다.

Q: 동형 문자열에 해시 맵이 두 개 필요한 이유는 무엇인가요?

s 에서 t 로의 매핑은 s 의 한 문자가 두 가지 방식으로 이름이 바뀌는 경우를 찾아냅니다. 하지만 ab 와 aa 처럼 s 의 두 문자가 같은 문자로 이름이 바뀌는 경우는 찾아내지 못합니다. t 에서 s 로의 역방향 매핑은 그 경우를 찾아냅니다.

Q: 동형 관계는 대칭적인가요?

네. 일대일 이름 변경은 되돌릴 수 있으므로, s 가 t 로 이름이 바뀐다면 모든 이름을 반대로 바꾸면 t 가 다시 s 로 돌아옵니다. isIsomorphic(s, t) 와 isIsomorphic(t, s) 는 항상 같은 결과를 냅니다.

Q: 두 문자열이 동형인지 또 어떻게 확인할 수 있을까요?

각 문자를 처음 나타나는 위치로 바꾸고 결과를 비교하세요. noon 과 deed 는 모두 0 1 1 0 이 되지만, moon 은 0 1 1 3 이 됩니다. 시간 복잡도는 O(n) 이며, 두 패턴에 O(n) 의 메모리를 사용합니다.

쉬움해싱

+10

첫 번째 문자열의 문자를 바꾸어 두 번째 문자열을 만들 수 있으면 두 문자열은 동형입니다. 같은 문자는 모두 동일한 새 이름으로 바뀌고, 서로 다른 두 문자가 같은 이름을 갖는 일은 없으며, 문자는 원래 이름을 그대로 유지할 수도 있습니다. 길이가 같은 두 문자열 s와 t가 동형이면 true를, 그렇지 않으면 false를 반환하세요.

함수

isIsomorphic(s: string, t: string) → boolean

sstring: 이름을 바꿀 문자열, 문자와 숫자
tstring: 도달해야 할 문자열, s와 길이가 같음
반환값boolean: s의 문자를 일대일로 바꾸어 t를 만들 수 있으면 true

제약 조건

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s와 t에는 영문자와 숫자만 포함됩니다. 대문자와 소문자는 서로 다른 문자입니다.

예제

입력: s = "noon"t = "deed"
출력: true
설명: n을 d로, o를 e로 이름을 바꾸세요. 모든 위치에서 이 이름 변경이 일치하며, 두 글자는 서로 다른 이름을 갖게 됩니다.

입력: s = "moon"t = "deed"
출력: false
설명: 왼쪽에서 오른쪽으로 보면 m은 d가 되고 o는 e가 되며, 그러면 n도 d가 되어야 합니다. 서로 다른 두 글자가 같은 이름을 가질 수 없으므로 답은 false입니다.

입력: s = "r2d2"t = "c3p3"
출력: true
설명: r는 c가 되고, 2는 3이 되며 d는 p가 됩니다. 숫자도 문자이며, 두 2 모두 3이 됩니다.

후속 질문

단어 목록이 주어졌을 때, 모든 단어 쌍을 비교하지 않고도 서로 동형인 단어들을 함께 그룹화할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

이름 변경은 양방향으로 이루어져야 합니다. s의 각 문자는 t의 문자 하나로 바뀌고, t의 각 문자는 s의 문자 하나에서 와야 합니다. 방향별로 하나씩 두 개의 매핑을 사용하면 한 번의 순회로 양쪽을 모두 확인할 수 있습니다.

모든 위치 쌍을 비교합니다

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

이름 변경은 같은 문자는 계속 같게, 다른 문자는 계속 다르게 유지합니다. 따라서 위치 i와 j의 모든 쌍에 대해 s[i] == s[j]이면 t[i] == t[j]와 같은 결과가 나와야 합니다. 이것으로도 충분합니다. 모든 쌍이 일치하면 s의 각 문자를 해당 위치에 있는 t의 문자로 바꾸는 것이 잘 정의되며, 두 문자에 같은 이름을 부여하는 일도 없습니다. moon과 deed에서는 위치 0과 3의 s 문자는 서로 다르지만 t에서는 둘 다 d이므로 답은 false입니다.

쌍은 약 n²/2개입니다. n = 2 × 10^4일 때, 어떤 쌍도 반복문을 일찍 멈추게 하지 않는다면 비교 횟수는 2 × 10^8회입니다.

알고리즘

모든 인덱스 i를 순회하고, 각 인덱스에 대해 그 이후의 모든 인덱스 j를 순회합니다.
s[i]가 s[j]와 같은지, 그리고 t[i]가 t[j]와 같은지 확인합니다.
두 결과가 다르면 false를 반환합니다.
마지막 쌍을 확인한 후 true를 반환합니다.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

두 개의 맵, 방향마다 하나씩

핵심 아이디어

읽으면서 이름 변경을 구성하세요. sToT는 s의 각 문자가 무엇으로 바뀌었는지 기록하고, tToS는 t의 각 문자가 어디에서 왔는지 기록합니다. a = s[i]와 b = t[i]인 위치 i에서 둘 다 새 문자라면 서로 연결하고, 그렇지 않다면 이미 서로를 가리키고 있어야 합니다.

맵 하나만으로는 충분하지 않습니다. sToT만 사용하면 moon과 deed는 통과합니다. s의 어떤 문자도 두 가지 방식으로 바뀌지 않기 때문입니다. 문제는 m과 n이 모두 d로 바뀐다는 점이며, 위치 3에서 tToS는 이미 d가 m에서 왔다고 기록하고 있습니다.

각 위치에서 몇 번의 맵 연산이 필요하므로 시간 복잡도는 O(n)입니다. 모든 문자 코드는 128보다 작으므로 각 맵은 128개 항목의 배열로 만들 수 있습니다. 따라서 공간 복잡도는 O(1)입니다. R 및 Swift 버전은 먼저 문자열을 코드 배열로 복사하며, 이 과정에는 O(n)이 걸립니다.

알고리즘

빈 맵 sToT와 tToS를 만듭니다.
각 인덱스 i에 대해 a = s[i]와 b = t[i]로 둡니다.
a가 sToT에 없고 b가 tToS에 없으면 a를 b에 매핑하고 b를 a에 매핑합니다.
그렇지 않으면 sToT[a]가 b가 아니거나 tToS[b]가 a가 아닌 경우 false를 반환합니다.
마지막 인덱스 이후에 true를 반환합니다.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

함정과 경계 사례

s에서 t로의 매핑 하나를 유지합니다. moon과 deed, 그리고 ab와 aa를 허용합니다.
각 문자가 나타나는 횟수를 비교합니다. abcabc와 xyzxzy는 모두 세 문자를 각각 두 번 사용하지만, 두 번째 b는 첫 번째 b가 y 위에 있던 것과 달리 z 위에 있습니다.
대소문자를 구분하지 않는 것으로 처리합니다. aA에는 서로 다른 두 문자가 있으므로 bb가 될 수 없습니다.
a부터 z까지만 배열 매핑의 크기를 설정합니다. 대문자와 숫자는 이 범위를 벗어나므로, 128개의 항목을 사용해 전체 문자 코드로 인덱싱합니다.

자주 묻는 질문4

동형 문자열(Isomorphic Strings)의 시간 복잡도는 무엇인가요?

두 맵을 사용하는 풀이에서는 각 위치를 한 번씩만 읽으므로 실행 시간은 O(n)입니다. 맵에는 가능한 문자(영문자와 숫자 62개)마다 항목이 최대 하나씩 저장되므로 추가 공간은 O(1)입니다. 모든 위치 쌍을 비교하면 O(n²)의 시간이 걸립니다.

동형 문자열에 해시 맵이 두 개 필요한 이유는 무엇인가요?

s에서 t로의 매핑은 s의 한 문자가 두 가지 방식으로 이름이 바뀌는 경우를 찾아냅니다. 하지만 ab와 aa처럼 s의 두 문자가 같은 문자로 이름이 바뀌는 경우는 찾아내지 못합니다. t에서 s로의 역방향 매핑은 그 경우를 찾아냅니다.

동형 관계는 대칭적인가요?

네. 일대일 이름 변경은 되돌릴 수 있으므로, s가 t로 이름이 바뀐다면 모든 이름을 반대로 바꾸면 t가 다시 s로 돌아옵니다. isIsomorphic(s, t)와 isIsomorphic(t, s)는 항상 같은 결과를 냅니다.

두 문자열이 동형인지 또 어떻게 확인할 수 있을까요?

각 문자를 처음 나타나는 위치로 바꾸고 결과를 비교하세요. noon과 deed는 모두 0 1 1 0이 되지만, moon은 0 1 1 3이 됩니다. 시간 복잡도는 O(n)이며, 두 패턴에 O(n)의 메모리를 사용합니다.

def isIsomorphic(s, t):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

s = "noon"
t = "deed"

예상 출력

true