leetcode/ 205. Isomorphic Strings

Description

Isomorphic Strings - LeetCode

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

 

---

Process

Constraints:

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s and t consist of any valid ascii character.

 

nums.length의 범위가 5*10^4으로 O(n^2)으로 풀면 무리가 있을 수 있겠다.

 

주어진 두 문자열이 매핑될 수 있는지 구하는 문제다. 처음에는 딕셔너리만으로 풀 수 있을 줄 알았는데 s = "abcep", t = "apple" 과 같은 경우 딕셔너리만으로 구현하면

convert = {
    "a" : "a",
    "b" : "p",
    "c" : "p",
    "e" : "l",
    "p" : "e"
}

 

과 같이 매핑되는 결과가 발생한다. 즉 중복 매핑이 발생해 변환 불가능한 문자열임에도 True가 반환되었다. 이미 매핑된 문자를 어떻게 감지할 수 있을까를 고민하다가 set을 사용했다. 리스트의 경우 in 연산 시 시간 복잡도가 O(n)이므로 고려하지 않았고 딕셔너리의 경우 value가 굳이 필요하지 않으므로 (이미 위에서 검증하므로) set을 선택했다.

또한 처음 구현 시 replace를 써서 문자열을 변환하는 연산을 수행하려고 했었지만 풀이 도중 그럴 필요가 없다는 것을 깨닫고 그냥 체크만 진행하도록 했다.

---

Solution: Time: 31 ms (97.30%), Space: 14.2 MB (40.50%)

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        convert = {}
        used = set()
        for i in range(len(s)):
            if s[i] in convert:
                if convert.get(s[i]) != t[i]:
                    return False
            else:
                if t[i] in used:
                    return False
                convert[s[i]] = t[i]
                used.add(t[i])
        return True

 

1. 매핑 정보를 저장할 딕셔너리 convert와 중복 매핑 여부를 판단할 set used를 선언한다

2. 문자열을 순회한다

2-1. 해당 문자와 매핑된 문자가 있다면 == convert 딕셔너리 안에 문자가 있다면

2-1-1. 해당 value가 변환되어야 할 문자 t[i]와 같은지 비교하고 다르다면 False를 반환한다

2-2. 매핑된 문자가 없는 경우 

2-2-1. 변환되어야 할 문자(t[i])가 이미 다른 문자와 매핑되었다면 == used에 저장되어 있다면 -> 중복 매핑이 불가능하므로 False를 반환한다

2-2-2. used에 변환되어야 할 문자(t[i])가 없다면 -> convert에 s[i] 매핑 정보를, used에 t[i]의 사용 정보(중복 검증용)를 저장한다

3. 문자열을 문제 없이 순회했다면 True를 반환한다

---

Conclusion

코드 설계를 계속 헐렁하게 하고 있다. 매번 테스트 케이스에서 하나씩 걸리면서 계속 코드를 수정하고 있는데....... 이런 꿈 같은 방향 제시는 어디에서도 기대할 수 없다 ㅠ 늦게 풀어도 괜찮으니까 충분히 고민하는 시간을 가지고 설계에 더 힘을 써서 문제 풀이를 진행하자 반성반성