[Leetcode/파이썬] 205. Isomorphic Strings

Isomorphic Strings

---

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

Explanation:

The strings s and t can be made identical by:

• Mapping 'e' to 'a'.
• Mapping 'g' to 'd'.

Example 2:

Input: s = "f11", t = "b23"

Output: false

Explanation:

The strings s and t can not be made identical as '1' needs to be mapped to both '2' and '3'.

Example 3:

Input: s = "paper", t = "title"

Output: true

 

Constraints:

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

 

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_map = {}
        t_map = {}

        for i in range(len(s)) :
            if s[i] not in s_map :
                s_map[s[i]] = t[i]

            else :
                if s_map[s[i]] == t[i] :
                    continue
                else :
                    return False

        for i in range(len(t)) :
            if t[i] not in t_map :
                t_map[t[i]] = s[i]
            else :
                if t_map[t[i]] == s[i] :
                    continue
                else :
                    return False
        
        return True

이 문제는 한 번 더 고민을 해봐야 하는 문제라서 easy 문제이지만 난이도가 조금 있다 생각한다. 

구현은 다음과 같이 하면 된다. 

s와 t의 각 문자별로 비교할 해시 테이블을 하나씩 만든다. 

s 먼저 for 문을 돌면서 현재 s_map에 없는 s[i]이면 s[i]:t[i] 가 되도록 s_map에 담는다. 이 담는 과정에서 이전에 담았던 적이 있는 문자가 나왔는데 다르다면, return False을 한다.

t 도 마찬가지로 t_map에 t[i]:s[i]가 되도록 담는다. 이 담는 과정에서 이전에 담았던 적이 있는 문자가 나왔는데 다르다면, return False을 한다.

어 이러면 안되는거 아니야? 라고 생각할 수 있다. 다시 한 번 생각해보자. 첫번째로 s_map[s[i]] != t[i] 이면 False이다. 하지만, 반대로 t_map[t[i]] == s[i] 가 성립할 수 있을까? 반대로는 성립하는데 전자로 성립을 하지 않는다면 이 자체로도 False 이다. 이 반대도 마찬가지 s_map[s[i]] == t[i] 가 성립하는데 t_map[t[i]] != s[i]이면 그렇다. 

그럼 한 번만 하면 되지 않느냐 라고 할 수 있다. 그 예시로 두 번째 예시를 반대로 해보자. s = 'b23', t='f11' 이면 s_map[s[i]] == t[i] 는 성립해도 t_map[t[i]] != s[i] 인 상황이 발생한다. 그렇기 때문에 두개를 만들어서 돌려보는 것이 중요하다. 

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_map = {}
        t_map = {}

        for i in range(len(s)) :
            if s[i] not in s_map :
                s_map[s[i]] = t[i]

            else :
                if s_map[s[i]] == t[i] :
                    continue
                else :
                    return False

            if t[i] not in t_map :
                t_map[t[i]] = s[i]

            else :
                if t_map[t[i]] == s[i] :
                    continue
                else :
                    return False
        
        return True

그냥 for 문 하나로도 충분하구나...