LeetCode - 205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/?envType=study-plan&id=level-1 

Isomorphic Strings - LeetCode

 

첫번째 잘못된 내 풀이

t[i]가 이미 다른 s의 char와 매칭되었을 가능성을 고려하지 못했음.

이를 수정하여 아래와 같이 풂.

 

두번째 수정한 내 풀이

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # dictionary 통해서 mapping 해보자.
        # key가 s에서의 char, value가 t에서의 char
        s_len = len(s)
        t_len = len(t)
        if (s_len!=t_len):
            return False
        
        my_dict = {}
        for i in range(s_len):
            if (s[i] in my_dict.keys()) and (my_dict[s[i]]!=t[i]):
                return False
            elif (s[i] not in my_dict.keys()) and (t[i] in my_dict.values()):
                return False
            else:    
                my_dict[s[i]]=t[i]
                
        return True

근데 속도가 하위 70%면 좀...ㅠ

시간복잡도 개선할 수 있는 방법 고민고민

 

 

세번째 개선된 내 풀이

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # dictionary 통해서 mapping 해보자.
        # key가 s에서의 char, value가 t에서의 char
        s_len = len(s)
        t_len = len(t)
        if (s_len!=t_len):
            return False
        
        my_dict = {}
        for i in range(s_len):
            if s[i] in my_dict: # key는 바로 이렇게 직접적으로 search 가능
                if (my_dict[s[i]]!=t[i]):
                    return False
            else:
                if t[i] in my_dict.values():
                    return False
                else:    
                    my_dict[s[i]]=t[i]
                
        return True

오 keys() 삭제하고 if else 문들 정리했더니 속도 상위 18%로 올라감