JavaScript로 LeetCode 290번 문제 해결하기: Word Pattern의 비결과 풀이법

LeetCode 290: Word Pattern 문제 해결하기

LeetCode 문제 중 하나인 Word Pattern은 문자열과 관련된 문제로, 특정한 패턴에 맞추어 문자열을 전환 및 대응시키는 작업을 요구합니다. 이번 포스팅에서는 JavaScript를 활용하여 이 문제를 단계별로 해결하는 방법을 소개하겠습니다. 문제 해결의 기본 개념부터 상세한 구현 방법까지 깊이 있게 다루어 보겠습니다.

문제 설명

Word Pattern 문제는 두 가지 입력값을 처리합니다:

1. 패턴 문자열 (pattern): 소문자인 문자로만 구성되어 있습니다.
2. 문자열 s: 띄어쓰기로 구분된 단어들의 집합입니다.

이 문제의 목표는 문자열 s가 패턴에 맞추어 일대일 대응 관계를 이루는지 확인하는 것입니다. 각 문자와 단어는 정확히 하나씩 매핑되어야 하며, 겹치지 않아야 합니다. 즉, 하나의 문자는 하나의 단어로만, 그리고 하나의 단어는 하나의 문자로만 매핑되어야 합니다. 이것은 일대일 대응을 의미하는 'bijective mapping'을 요구합니다.

예제

예제 1

• 입력:
  • pattern = "abba"
  • s = "dog cat cat dog"
• 출력: true
• 설명: 'a'는 "dog"에, 'b'는 "cat"에 매핑됩니다.

예제 2

• 입력:
  • pattern = "abba"
  • s = "dog cat cat fish"
• 출력: false
• 설명: 'a'와 "dog"는 매핑되었지만 'b'는 동일한 "cat"에 매핑되지 않은 "fish"와 겹칩니다.

예제 3

• 입력:
  • pattern = "aaaa"
  • s = "dog cat cat dog"
• 출력: false
• 설명: 'a'는 여러 다른 단어로 매핑될 수 없습니다.

JavaScript 코딩을 통한 문제 해결

이 문제를 해결하기 위해 우리는 두 개의 해시맵을 사용할 것입니다. 다음과 같은 전략을 사용하여 명확한 매핑을 구현합니다.

JavaScript 구현 코드

var wordPattern = function(pattern, s) {
    const words = s.split(" ");
    if (pattern.length !== words.length) return false;

    const charToWord = new Map();
    const wordToChar = new Map();

    for (let i = 0; i < pattern.length; i++) {
        const char = pattern[i];
        const word = words[i];

        if ((charToWord.has(char) && charToWord.get(char) !== word) || 
            (wordToChar.has(word) && wordToChar.get(word) !== char)) {
            return false;
        }

        charToWord.set(char, word);
        wordToChar.set(word, char);
    }

    return true;
};

작동 원리

1. 단어 분할: s.split(" ")을 사용하여 문자열 s를 분할해 배열로 만듭니다.
2. 길이 확인: 패턴의 길이와 단어 배열의 길이가 다르면 false를 반환합니다.
3. 맵 설정:
   • 각 패턴의 문자와 단어를 charToWord 맵에 저장합니다.
   • 각 단어와 패턴의 문자를 wordToChar 맵에 저장합니다.
4. 매핑 검증: 두 맵에서 적절한 매핑이 이루어지지 못하면 false를 반환합니다.
5. 결과 리턴: 모든 매핑이 올바르면 true를 반환합니다.

복잡도 분석

• 시간 복잡도: O(n) - 패턴의 길이 또는 단어의 수가 n입니다.
• 공간 복잡도: O(1) - 고유한 문자와 단어의 수에 관계없이 해시맵에서 저장 공간은 변하지 않습니다.

드라이 런 (Dry Run)

• 입력: pattern = "abba", s = "dog cat cat dog"
• 출력: true

인터뷰에서 고려하면 좋은 팁

• 두 개의 맵 설명: char to word, word to char의 맵핑을 설명하여 서로의 일관성을 유지해야 함을 강조하세요.
• 경계 사례 논의:
  • 패턴과 s의 길이가 다른 경우.
  • 중복 매핑의 처리 문제.
• 확장 방법:
  • 여러 문자의 패턴이나 여러 단어로의 확장 가능성을 논의하세요.

추가로 도움이 될 자료

이 문제와 관련된 더 많은 설명과 JavaScript 코드를 공부하려면 아래의 링크를 참조하십시오:

• Isomorphic Strings - JavaScript Solution