[LeetCode] 205. Isomorphic Strings

문제 출처: https://leetcode.com/problems/isomorphic-strings/

Isomorphic Strings - LeetCode

 

문제

두 문자열 s와 t가 주어지면, 동일 구조의 문자열인지 아닌지 결정하라.

 

두 문자열 s와 t가 만약 s의 문자들을 다른 문자로 대체했을 때 t를 얻을 수 있다면 동일 구조라 한다.

 

모든 문자의 발생빈도는 다른 문자와 순서를 유지하면서 대체되어야 한다. 두 문자가 동일 문자로 매핑되어서는 안 되지만, 한 문자가 자신과 매핑될 수 있다.

 

예제

Input: s = "paper", t = "title"
Output: true

Input: s = "foo", t = "bar"
Output: false

 

풀이

문자열 s와 t를 순회하면서 s의 문자와 t 문자를 매핑해간다. 매핑 과정에서 한가지 확인해줘야 하는 건, s[i] 문자가 이전에 어떤 문자와 매핑이 되었던 적이 있는지, 있다면 현재 매핑하려고 하는 문자 t[i]와 동일한 문자인지 체크하는 것이다.

 

현재까지의 내용을 코드로 작성하면 아래와 같다.

var isIsomorphic = function(s, t) {
    const sDic = new Map();
    for (let i = 0; i < s.length; i++) {
        if (sDic.has(s[i]) && sDic.get(s[i]) != t[i]) {
            return false;
        }    
        sDic.set(s[i], t[i]);
    }
    return true;
}

이 코드를 제출하게 되면, s = "badr", t = "babc"에서 틀린 답을 내놓는다. 그 이유는 아래와 같다.

s = "badr", t = "babc"

1) s[0] -> t[0] 매핑 : b -> b
2) s[1] -> t[1] 매핑 : a -> a
3) s[2] -> t[2] 매핑 : d -> b        => s 문자열의 b와 d가 동일한 문자인 b 문자로 매핑되는 문제 발생!!!!
4) s[3] -> t[3] 매핑 : r -> c

문자열 s의 3번째 문자 d가 t의 3번째 문자 b와 매핑시키면, s이 첫 문자 b와 세 번째 문자 d가 문자 b로 매핑되는 문제가 발생하는데 이를 탐지하는 부분이 없기 때문이다.

 

이 문제를 해결하기 위해서 t의 문자가 s의 어떤 문자와 매핑되어 있는지에 대한 추가 정보를 저장할 필요성이 있고, 이를 이용하여 다음의 코드와 같이 문제를 해결할 수 있다.

var isIsomorphic = function(s, t) {
    const sDic = new Map();    // s[i]가 어떤 문자와 매핑되는지 저장
    const tDic = new Map(); // t[i]는 s의 어떤 문자와 매핑되어 있는지 저장

    for (let i = 0; i < s.length; i++) {
        if (sDic.has(s[i]) && sDic.get(s[i]) != t[i]) {
            return false;
        }

        if (!sDic.has(s[i])) {
            // t[i]문자로 매핑되어 있는 s 문자가 있는지 체크
            // 있다면, 현재 s[i]와 동일한 문자인가?
            if (tDic.has(t[i]) && tDic.get(t[i]) != s[i]) { return false; }

            sDic.set(s[i], t[i]);
            tDic.set(t[i], s[i]));
        }
    }
    return true;
}

 

 

Github: 205.js

opwe37/Algorithm-Study