LeetCode | Isomorphic Strings

송치헌·2021년 7월 13일

Algorithm | LeetCode

목록 보기

5/15

문제

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:
Input: s = "egg", t = "add"
Output: true
Example 2:
Input: s = "foo", t = "bar"
Output: false
Example 3:
Input: s = "paper", t = "title"
Output: true
Constraints:

$1 <= s.length <= 5 * 10^4$
t.length == s.length
s and t consist of any valid ascii character.

Python 풀이

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        dict = {}
        for i in range(len(s)):
            if s[i] in dict:
                if t[i]!=dict[s[i]]:
                    return False
            else:
                if t[i] in dict.values():
                    return False
                else:
                    dict[s[i]] = t[i]
        return True

문제 설명

2개의 같은 길이의 문자열 s와 t가 주어진다. 두 문자열이 동형인지 아닌지 판별하는 문제이다.

isomorphic : being of identical or similar form, shape, or structure

우리 말로 동형이라고 불린다. 즉, 그냥 같은 형태인지 판별하면 된다. 현대대수학 수업시간에 많이 들어본 용어인데 수학적으로 접근할 문제는 아니므로 설명은 패스.

문제 설명으로 돌아와서, Example 1을 보면

Input: s = "egg", t = "add"
Output: true

egg와 add는 동형이라고 한다. 이렇게만 봐도 감이 잡히겠지만 부연 설명하자면, 한 알파벳이 다른 알파벳과 일대일 대응이면서 일대일 함수이다.

즉, e는 a, g는 d와 매핑된다.

만약 s = 'egg', t = 'apt' 이면 어떻게 될까

e -> a
g -> p
g -> t

이걸 다시 써보면

e -> a
g -> p,t

g가 p와 t 두개에 대응되므로 동형이 아니다.

이번엔
s = 'age', t = 'odd' 일 경우는 어떻게 될까

a -> o
g -> d
e -> d

이걸 다시 써보면

a -> o
g,e -> d

하나의 알파벳이 하나씩 대응되지 않기 때문에 동형이 아니다.

이제 어떻게 풀어야 할지 감이 잡혔다. dictionary로 각 알파벳을 하나씩 대응시켜 주면서 이미 딕셔너리에 대응이 되어 있는데 현재 비교할 문자가 딕셔너리에 대응되어 있는 관계와 다르면 False를 반환하면 된다. 문자열 끝까지 비교했을 때 아무 이상이 없으면 True를 반환하면 된다.

코드 설명

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        dict = {}
        for i in range(len(s)):
            if s[i] in dict:
                if t[i]!=dict[s[i]]:
                    return False
            else:
                if t[i] in dict.values():
                    return False
                else:
                    dict[s[i]] = t[i]
        return True

빈 딕셔너리를 하나 만들고 문자열을 처음부터 끝까지 돌면서 s와 t를 비교할 것이다. 어차피 s와 t는 제한 조건에서 길이가 같다고 했으므로 길이는 상관 없다.

s = 'egg' , t = 'add'

딕셔너리에 현재 비교할 문자가 있는지 물어봤는데 현재 아무것도 없기 때문에 아래 else로 간다.
t[i]('a')가 dict_values 에 있는지 물어봤는데 빈 딕셔너리기 때문에 아래 else에서 현재 문자를 사전에 추가해 준다.
e -> a
이제 g와 d를 비교할건데 g도 딕셔너리 key에 없기 때문에 else로 간다. d가 또 딕셔너리 value에 없기 때문에 딕셔너리에 추가해준다.
마지막으로 또 g와 d를 비교하는데, g가 딕셔너리 key에 존재하기 때문에 현재 비교하는 t[i]('d')가 dict[s[i]]('d')와 다른지 본다. 같기 때문에 for문이 끝나고 True가 된다.