[2024] day 94. Leetcode 205. Isomorphic Strings

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 2일 (화)
Leetcode daily problem

205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/?envType=daily-question&envId=2024-04-02

Problem

Solution

array

두 개의 문자열 s와 t가 주어지면 두 문자열이 동형(Isomorphic)인지 확인한다.s의 문자를 대체하여 t를 얻을 수 있으면 두 문자열 s와 t는 동형이다.
문자의 순서를 유지하면서 모든 문자를 다른 문자로 바꿀 수 있어야 한다.

한 문자열(s)의 모든 해당 문자가 두 번째 문자열(t)의 문자로 대체될 수 있어야 하며, 두 문자가 같은 문자로 매핑되어서는 안된다.

Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sList, tList = [], []
        
        for idx in s:
            sList.append(s.index(idx))
        for idx in t:
            tList.append(t.index(idx))
        
        return sList == tList

Complexicity

시간 복잡도

첫 번째 for 루프에서는 문자열 s의 각 문자에 대해 index() 함수를 사용하여 해당 문자의 인덱스를 찾는 과정이 문자열의 길이에 비례하므로 O(n) 이다.
이러한 과정을 두 번 하고, 그 이후 두 리스트 sList와 tList의 비교는 두 리스트의 길이가 같은지 확인하는 작업도 O(n) 시간이 소요된다.
총 시간 복잡도는 O(n)이다.

공간 복잡도

sList와 tList 두 개의 리스트를 사용해서, 각 s와 t의 문자의 인덱스를 저장하므로, 리스트의 크기는 각 입력 문자열의 s,t의 길이이므로 공간복잡도는 O(n)이다.

---

그 외에 python 내장 함수를 이용해 손쉽게 풀 수 있는 방법이 있다.

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

zip, set의 내장함수를 사용해서 세 개의 집합의 길이를 비교하여, s와 t가 같은 패턴을 가지고 있는지를 확인할 수 있다.
문자열 s와 t를 set으로 변환해 중복을 제거한다. 그 뒤에
zip함수로 s,t의 요소들을 하나씩 조합해 tuple을 생성하고 중복을 제거한다.
이렇게 생성된 집합은 문자열 s와 t가 같은 패턴을 가지고 있는 경우 서로 대응되는 문자들의 조합이 유일하게 매핑되므로 중복된 요소가 없을 것이다.
따라서 이 집합의 길이가 s와 t에서 서로 다른 문자의 개수를 나타낼 것이다.

해당 코드의 시간복잡도는 문자열 s,t의 문자를 튜플로 묶을 때 가장 작은 길이에 의해 결정되어 O(min(len(s), len(t))) 시간이 소요되고,
중복 제거를 위해 모든 튜플을 확인해야 하므로 이 연산은 O(min(len(s), len(t))) 시간이 소요된다.
len(set(zip(s, t))), len(set(s)), len(set(t)): 각각 집합(set)의 길이를 구할떄는 O(1) 시간이 소요된다.

공간복잡도는
각 집합(set)을 생성하는데, 중복을 제거하기 위한 새로운 데이터 구조를 생성한다. 이들 집합의 크기는 각각 입력 문자열의 길이에 의존하며, 따라서 공간 복잡도는 O(min(len(s), len(t)))이다.
따라서 주어진 코드의 전체 공간 복잡도는 O(min(len(s), len(t)))이다.