[LeetCode] 205. Isomorphic String (Python)

Problem

Solution

Array

두 개의 문자열 s, t가 동형(isomorphic)인지 확인하는 문제. s에 존재하는 문자를 가지고 t를 만들 수 있으면 두 문자열 s, t는 동형이다. 단, 문자의 순서를 유지하며 모든 문자를 다른 문자로 바꿀 수 있어야한다. 두 문자가 같은 문자로 맵핑되어서는 안된다.

 

처음에 dictionary로 character 개수만 카운트해서 비교했는데 알고보니 문제 이해를 잘 못했다.

엣지 케이스인 s = bbbaaaba, t = aaabbbba 에서 마지막에서 두번째 문자에서 조건을 만족하지 못하므로 false

Code

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

        if len(s) != len(t):
            return answer

        for idx in s:
            sLi.append(s.index(idx))

        for idx in t:
            tLi.append(t.index(idx))

        if sLi == tLi:
            answer = True
        return answer

 

Complexity

Time Complexity

첫번째 for 문에서 문자열 s의 길이만큼 반복문을 도므로 O(N)이다.

문자열 t 도 마찬가지.

그 다음으로 두 리스트의 길이를 비교할 때도 O(N)이므로 총 시간 복잡도는 O(N)이다.

 

Space Complexity

s, t문자열 각각 문자열의 길이만큼 리스트를 사용하므로 공간 복잡도는 O(N) 이다.

 

 

참고

https://velog.io/@heyggun/2024-day-93.-Leetcode-205.-Isomorphic-Strings