[Leetcode] 205. Isomorphic Strings - JS

https://leetcode.com/problems/isomorphic-strings/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- s, t 두 문자열이 주어질 때, 이들이 isomorphic(동형)인지 판단하라.
- s의 문자를 대체하여 t의 문자로 바꿀 수 있으면 isomorphic(동형)이다.
- 문자의 순서를 유지하면서 다른 문자로 바껴야 한다.

제한조건
--------------------
- 1 <= s.length <= 5*10^4
- t.length === s.length
- s, t는 유효한 아스키 코드로 구성된다.

 

2. 접근 방법

접근방법
--------------------
두 문자열의 길이는 동일하므로 각 문자열이 포함한 유일한 문자의 갯수가 동일한지 판단한다.
예를 들어, t 문자열은 3가지 문자로 이뤄져있고 s 문자열은 4가지 문자로 이뤄져있으면
t로는 s문자열을 만들 수 없으므로 false이다.

예외 ❗️
s = 'bbbaaaba'
t = 'aaabbbba'

s문자열의 'b' -> 'a', 'a' -> 'b'로 바꾸면
'aaabbbab' 이므로 t와 다르므로 false
hash의 key 갯수는 동일하지만 동형은 아니다.
동형을 판단하려면 위치(index)까지 고려해야한다.

 

 

3. 코드

var isIsomorphic = function(s, t) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (!Object.values(hash).includes(t[i])) {
            hash[s[i]] = t[i];
        }
    }

    // 각 인덱스마다 s문자열을 t문자열로 변환했을때, t와 같은지 비교
    for (let i = 0; i < s.length; i++) {
        if (hash[s[i]] !== t[i]) return false;
    }

    return true
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n^2)

- 공간복잡도: O(n)

 

매번 hash에 문자를 등록할 때 마다 hash의 value 값들을 순회해서 체크하므로, 최악의 경우 시간 복잡도가 O(N^2)이다.

시간 복잡도를 개선해서 풀어보자.

 

5. 복잡도 개선된 풀이

var isIsomorphic = function(s, t) {
    let hash = {};
    let reversedHash = {};

    for (let i = 0; i < s.length; i++) {
        const charS = s[i];
        const charT = t[i];

        if (!hash[charS]) {
            hash[charS] = charT;
        } else if (hash[charS] !== charT) {
            return false;
        }

        if (!reversedHash[charT]) {
            reversedHash[charT] = charS;
        } else if (reversedHash[charT] !== charS) {
            return false;
        }
    }
    return true;
};

 

s와 t 문자열을 매핑한 hash와 반대로 매핑한 reversedHash를 선언한다.

각 hash에 매핑된 문자열이 없으면 초기값으로 추가해주고

만약 존재하는데, 매핑된 값이 다르면 false를 반환해준다.

모든 반복문이 종료되었다면 true를 반환한다.

 

위 코드는 시간복잡도: O(n)으로 개선할 수 있다.