[Leetcode] 290. Word Pattern - JS

https://leetcode.com/problems/word-pattern/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 패턴과 문자열 s가 주어지면 s가 동일한 패턴을 따르는지 확인
- 패턴의 문자와 s의 비어 있지 않은 단어 사이에 전단사가 있는 완전 일치를 의미합니다.
- 패턴의 각 문자는 s에 있는 정확히 하나의 고유 단어에 매핑됩니다.
- s의 각 고유 단어는 패턴의 정확히 하나의 문자에 매핑됩니다.
- 두 글자가 같은 단어에 매핑되지 않으며 두 단어가 같은 글자에 매핑되지 않습니다.

제한조건
--------------------
- 1 <= patter.length <= 300
- pattern은 영어 소문자로 구성된다.
- 1 <= s.length <= 3000
- s는 영어 소문자, ' ' 공백으로 구성된다.
- s는 맨앞, 맨뒤는 ' ' 공백이 아니다.
- s 안의 모든 단어는 단일 공백으로 구분된다.

 

2. 접근 방법

접근방법
--------------------
- pattern의 문자를 s와 매핑하고 s의 문자를 pattern 문자와 매핑한 2개의 hash를 선언한다.
- 순회하면서 서로 매핑한 문자가 다르면 false를 반환하고 순회가 끝나면 true를 반환한다.

 

 

3. 코드

var wordPattern = function(pattern, s) {
    const hash = {};
    const reversedHash = {};
    // 예시에 'constructor'가 있어서 객체에 저장 시 예상치 못한 동작 발생 방지
    const splitedS = s.split(' ').map(s => s.toUpperCase())
    if (pattern.length !== splitedS.length) return false

    for (let i = 0; i < pattern.length; i++) {
        const patternChar = pattern[i];
        const sChar = splitedS[i];

        if (!hash[patternChar]) {
            hash[patternChar] = sChar;
        } else if (hash[patternChar] !== sChar) {
            return false;
        }

        if (!reversedHash[sChar]) {
            reversedHash[sChar] = patternChar
        } else if (reversedHash[sChar] !== patternChar) {
            return false;
        }
    }
    return true;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

[Leetcode] 205. Isomorphic Strings - JS 과 비슷한 문제여서 동일한 방법으로 접근했다.

하지만, 예시 중에 'constructor' 가 포함되어있었는데, 객체의 key 값으로 'constructor'를 등록할 경우,

생성자 함수처럼 동작하기 때문에 예상치 못하게 동작한다.

이를 해결하기 위해 대문자로 변경해준 뒤 매핑하였다.