Leetcode - 205. Isomorphic Strings

문제

주어진 두 문자열이 isomorphic 하면 true 아니면 false 리턴. (문자열을 구성하는 charactor는 모든 ascii문자)
https://leetcode.com/problems/isomorphic-strings/

Input: s = "egg", t = "add"
Output: true
Input: s = "abc", t = "xyz"
Output: true
Input: s = "foo", t = "bar"
Output: false
Input: s = "paper", t = "title"
Output: true
Input: s = "13", t = "42"
Output: true

해결 O(N)

처음에 이해가 안가서 몇 해설들을 참고했다. isomorphic한 두 문자열을 mapping했을때 생기는 독특한 규칙을 깨닫는 것이 핵심이다.(이걸 못 생각해 내서 힘들었다) 이 특징은 평상시에 다른 문제를 해결할때도 알아두면 유용할 것같다. 잘 배운듯! 이해한 내용을 아래와 같이 정리.

가령 "agg"와 "bcd"라는 문자열 두개가 있다고 하자. 만약 두 문자열이 isomorphic하다면 g는 반드시 하나의 문자와만 대응 되어야한다. 규칙을 일반화하면 하나의 uniq한 문자는 하나의 uniq한 문자와만 매핑된다. 이경우는 g가 c 도 매핑되고 d로도 매핑되기때문에 false이다. 따라서 이경우는 "agg"에 "bcd"를 매핑 하는 과정에서 true/false인지 알아낼 수 있다.

a -> b
g -> c
g -> d ?

그렇다면 "agg" 와 "bcc" 를 보자. g는 오직 c와만 대응이 된다. 따라서 true이다.

a -> b
g -> c
g -> c

마지막으로 "abc"와 "kcc"를 살펴보자. 하나의 uniq한 문자는 하나의 uniq한 문자와만 매핑된다 는 규칙이 지켜졌기 때문에 이는 true가 나오게 된다. 하지만 우리는 직관적으로 이 답은 false가 되어야함을 알고 있다.

a -> k
b -> c
c -> c

이 경우는 두가지 해결방법이 있다. 첫번째는 b와 c 모두 c를 가리키기 때문에, 사실상 하나의 문자가 하나의 문자와만 매핑된다는 규칙이 지켜지지 않았음을 체크 하는것이고. 두번째는 map을 두개를 만들어서, "abc"->"kcc"하나 그리고 "kcc"->"abc"하나를 추가로 만들어 동일한 방식으로 체크 하는 것이다. 두번째 방법으로 추가 매핑을 하면

k -> a
c -> b
c -> c ?

c가 b와 c 두개로 매핑이 되기 때문에 false가 됨을 알아낼 수 있다. 따라서 맵을 정방향 역방향 두개를 만들어서 계산하면 된다. 시간복잡도는 문자열을 리니어하게 탐색하면 해결되므로 O(N)이다. 이를 코드로 구현 하면 아래와 같다.

bool isIsomorphic(char * s, char * t){
    int map_s[128] = {0,}; // it can be all of ascii charactor
    int map_t[128] = {0,};
    int ssize = strlen(s);
    for (int i = 0; i < ssize; i++) {
        // 'a' must be mapped to a uniq character. (a -> b and a -> c) is false
        if (map_s[s[i]] && map_s[s[i]] != t[i])
            return false;
        map_s[s[i]] = t[i];
    }
    for (int i = 0; i < ssize; i++) {
        // opposit case is same.
        if (map_t[t[i]] && map_t[t[i]] != s[i])
            return false;
        map_t[t[i]] = s[i];
    }
    return true;
}

위 코드를 아래와 같이 개선 할 수 있고. 더 빠른 결과를 얻었다.
Runtime: 0 ms, faster than 100.00%
Memory Usage: 6 MB, less than 40.40%

bool isIsomorphic(char * s, char * t){
    int map_s[128] = {0,}; // it can be all of ascii charactor
    int map_t[128] = {0,};
    int ssize = strlen(s);
    for (int i = 0; i < ssize; i++) {
        // 'a' must be mapped to a uniq character. (a -> b and a -> c) is false
        if (map_s[s[i]] && map_s[s[i]] != t[i])
            return false;
        // opposit case is same.
        if (map_t[t[i]] && map_t[t[i]] != s[i])
            return false;
        map_s[s[i]] = t[i];
        map_t[t[i]] = s[i];
    }
    return true;
}