주어진 문자열 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 문제를 정리해봤습니다.
'컴퓨터 공부 > 📚 Leetcode' 카테고리의 다른 글
[리트코드/leetcode/python] 589. N-ary Tree Preorder Traversal (0) | 2023.05.23 |
---|---|
[리트코드/leetcode/python] 409. Longest Palindrome (0) | 2023.05.23 |
[리트코드/leetcode/python] 121. Best Time to Buy and Sell Stock (2) | 2023.05.20 |
[리트코드/leetcode/python] 21. Merge Two Sorted Lists (2) | 2023.05.20 |
[리트코드/leetcode/python] 392. Is Subsequence (0) | 2023.05.20 |