[LeetCode] 205. Isomorphic Strings (Daily Question)

문제

---

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.

 

주어진 두 문자열 s, t가 같은 구조인지 판별하는 문제이다.

 

예를 들면, egg와 add는 구조상(이런 구조:🐥🐧🐧)으로 볼 때 같다고 할 수 있다.

다른 예로, abbd와 bccb는 다르다고 할 수 있다.

---

 

풀이

---

아이디어

치환암호처럼 s의 각 문자를 t에 대해 매핑한다.

 

코드

# s의 각 문자를 t에 대해 매핑
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 매핑 테이블
        table = {}

        # 이미 매핑된 문자를 저장할 set (중복매핑 방지)
        used = set([])

        for sc, tc in zip(s, t):
            # 매핑 테이블과 일치하지 않은 경우
            if sc in table and table[sc] != tc:
                return False
            
            # 아직 매핑되지 않은 경우
            elif sc not in table:
                # 중복 매핑되는 경우
                if tc in used: 
                    return False
                table[sc] = tc
                used.add(tc)
            
            # else 매핑된 값이 일치한 경우 continue

        return True

중복 매핑은 같은 대상으로 매핑될 때를 말한다.

예를 들면, s=ac와 t=bb가 주어졌을 때 s의 a, c 모두 b로 매핑된다. (a->b, c->b)

 

---

 

후기

---

난이도

어떤 방식으로 풀 지 생각해내기만 한다면 구현하기에는 쉬운 문제였다.

예외상황도 딱히 없었기에 까다롭다는 느낌은 없었다.

 

다른 풀이

양쪽 문자열 모두 변환시켜 비교하는 방법이 있다.

ABCA -> 0120,   GOSG -> 0120

매핑테이블이 두 개가 필요하지만, 중복매핑을 고려할 필요는 없어진다.