[리트코드/leetcode/python] 205. Isomorphic Strings

이미지를 누르면 문제 링크를 보실 수 있습니다.

 

 

주어진 문자열 s와 t가 동형사상이라면, true를 반환하고, 그렇지 않으면, false를 반환하는 문제인데요!

 

다양한 문제풀이가 있을거에요. 딕셔너리를 이용해서 풀어도 되고, 자바를 활용한다면 해시맵으로도 풀 수 있을 것 같습니다!

저도 처음에는 딕셔너리로 접근을 했다가, index의 위치만 저장하는 리스트로 풀어도 되겠다 싶어서 리스트만을 이용했습니다.

 

코드를 보면서 살펴보겠습니다.

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

        if len(s) != len(t):
            return answer
        
        else:
            s_check = []
            t_check = []
            for i in s:
                s_check.append(s.index(i))

            for j in t:
                t_check.append(t.index(j))

            if s_check == t_check:
                answer = True
            
            return answer

s_check 과 t_check 리스트를 만들어주고,

s와 t를 순회하면서, 해당 문자의 index를 각 체크 리스트에 추가해줍니다.

index()함수는 문자열에서 해당 문자가 처음으로 나타나는 인덱스를 반환하기 때문에, 동형사상 문자열을 검사할 수 있겠죠.

 

저도 맨처음에는 딕셔너리의 키 값의 길이만을 비교하다가, 

aaabbbba 와 aaabbbab 라는 반례를 보고 코드를 수정했습니다. 두 문자열은 a와 b가 각각 4번씩 나왔지만, 동형사상 문자열이라고 볼 수 없는 것이 위치가 마지막에 살짝 좀 다르죠!

 

위 코드에서는 "문자열에서 해당 문자가 처음 나타나는 인덱스를 저장"하는 것이고, 그렇게 한다면 동형사상인지 아닌지를 보완할 수 있을 거에요!

 

리트코드에서 괜찮은 코드도 발견했는데요, 다른 코드도 살펴볼게요

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

 

* zip 함수 설명

파이썬의 내장 함수 zip()은 iterable, 즉 순회 가능한 객체를 인자로 받고 각 자료형의 각각의 요소를 나눈 후 인덱스끼리 잘라서 리스트로 반환해줍니다. - 여기서 말하는 iterable 자료형은 파이썬에서 리스트, 튜플 같은 반복 가능한 자료형을 의미합니다.

 

위 코드에서는 s와 t를 set()함수로 집합화 시킨 후, 그 길이가 같은지를 판별했고, 추가로, zip()함수로 (s,t) 쌍을 집합화해서 그것들의 길이도 비교했습니다.

위에서 살펴봤던 예시를 비교해보자면, aaabbbba 와 aaabbbab 에서

set(s) => {a,b} 이므로 len(set(s)) 는 2가 되겠고, len(set(t)) 도 마찬가지로 2가 됩니다.

하지만, set(zip(s,t))는 {(a,a), (b,b), (b,a), (a,b)}가 되고 이것들의 길이는 4가 되므로 false를 리턴하게 됩니다. zip함수로 동형사상까지 검사하는 효율높은 코드라고 할 수 있겠죠!?

 

이상 Isomorphic Strings 문제를 정리해봤습니다.