LeetCode 205(Isomorphic String, Python)

1. 문제 링크

• https://leetcode.com/problems/isomorphic-strings/

Isomorphic Strings - LeetCode

 

2. 문제 설명

• 두 문자열 s와 t가 주어졌을 때, 두 문자열이 isomorphic한지 Boolean값을 반환
  • isomorphic의 사전적 의미는 "동형" 형태가 같다는 의미이고, 
  • 해당 문제에서는, 문자열에서 특정 문자를 다른 문자로 바꾸는데, 문자의 순서가 유지되는지를 판단.
  • 예시를 보면 좀 더 직관적이다.
  • 예시1) s = "egg", t = "add"이면, 둘은 122, 122 형태이므로 True이다 
  • 예시2) s = "foo", t = "bar" 같은 경우는 동일 문자형태로 맵핑이 불가하여 False
  • 예시3) s = "paper", t = "title"의 경우, 12134, 12134로 변형이 가능하므로 True이다. 

 

3. 처음 풀이

• 이 문제를 보자마자 생각난 풀이는, s,t 각각에 dictionary를 두고, 동일한 문자가 나오면 value를 append 시켜주는 구조로 한 뒤
• 두 dict의 key가 아닌 values()가 동일한지를 판별하는 방법이었다.
  • 예를들어, egg, add라면
    • egg에 대해서는 {'e':'0','g':'12'}, add에 대해서는 {'a':'0', 'd':'12'}로 두 dict의 value인 ['0','12']가 동일하기 때문에 True를 반환하는 구조로 짰다. 
  • 여기서 문제점은, 
    • s_dict.values() == t_dict.values()가 실제 값이 동일하더라도 False를 반환하는 것이었고,
    • 이는 검색해보니, python의 버전에 따라, values의 순서가 다를 수 있기 때문이라는 정보를 확인했다. 
  • 그래서,, list(s_dict.values()) == list(t_dict.values())를 return하였는데, 이 과정에서 시간이 오래걸려서 runtime이 좋진 않았던 풀이.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:

        s_dict = {}
        t_dict = {}

        index = 0 
        for i in s:
            if i not in s_dict:
                s_dict[i] = str(index)
                index += 1
            else:
                s_dict[i] = s_dict[i] + str(index)
                index +=1
        
        index = 0 
        for i in t:
            if i not in t_dict:
                t_dict[i] = str(index)
                index += 1
            else:
                t_dict[i] = t_dict[i] + str(index)
                index += 1

        return list(s_dict.values()) == list(t_dict.values())

 

4. 다른 풀이 

• 간단하고 깔끔했던 풀이
  
  • set(s)는 ['e','a'], set(t)는 ['a','d']를 반환해준다.
    • 만약, 두 문자열이 동형이라면, 중복 제외한 문자열의 개수는 동일할 것이다.
  • zip('egg','add')를 하면 [('e', 'a'), ('g', 'd'), ('g', 'd')]를 반환해준다.
    • 두 문자열에 대한 zip의 중복제외 개수는, 각 문자열의 중복 제외 문자열 개수와 동일할 것이다. (동형이므로)
  • 위 두가지 전제조건으로 아래와 같이 한줄의 코드로 return 가능

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
    return len(set(s)) == len(set(t)) == len(set(zip(s,t)))

 

5. 배운 점

• zip, set 적절히 사용하기!
  • 예전에 분명 비슷한 방식의 접근을 한 적이 있는데, 여기서 바로 떠올리지 못했다.