LeetCode Challenge: 290. Word Pattern - JavaScript Solution 🚀

#javascript #programming #leetcode #interview

Top Interview 150

The Word Pattern problem tests your ability to handle bijective mappings between characters and words. Let’s solve LeetCode 290: Word Pattern step by step.

🚀 Problem Description

Given:

A pattern string containing only lowercase letters.
A string s consisting of words separated by spaces.

Return true if s follows the same pattern as pattern, i.e.:

Each character in pattern maps to exactly one word in s.
Each word in s maps to exactly one character in pattern.

💡 Examples

Example 1

Input: pattern = "abba", s = "dog cat cat dog"  
Output: true  
Explanation: 'a' -> "dog", 'b' -> "cat".

Example 2

Input: pattern = "abba", s = "dog cat cat fish"  
Output: false  
Explanation: 'a' -> "dog", but 'b' cannot map to both "cat" and "fish".

Example 3

Input: pattern = "aaaa", s = "dog cat cat dog"  
Output: false  
Explanation: 'a' -> "dog", but then cannot map to "cat".

🏆 JavaScript Solution

We solve this problem using two hash maps:

To map each character in pattern to a word in s.
To ensure each word in s maps back to a unique character in pattern.

Implementation

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;
};

🔍 How It Works

Split Words:
- Split the string s into an array of words using split(" ").
Check Lengths:
- If the length of pattern does not match the number of words in s, return false.
Use Two Maps:
- Map each character in pattern to a word in s.
- Map each word in s back to a character in pattern.
Validate Mappings:
- If a character or word conflicts with an existing mapping, return false.
Return True:
- If all characters and words map consistently, return true.

🔑 Complexity Analysis

Time Complexity: O(n), where n is the length of pattern (or the number of words in s).
- Each character and word is processed once.
Space Complexity: O(1), where k is the number of unique characters and words.
- Two hash maps store up to k mappings.

📋 Dry Run

Input: pattern = "abba", s = "dog cat cat dog"

Output: true

✨ Pro Tips for Interviews

Explain Two Maps:
- Highlight how mapping both char -> word and word -> char ensures consistency.
Discuss Edge Cases:
- pattern and s lengths differ: pattern = "abba", s = "dog cat".
- Duplicate mappings: pattern = "ab", s = "dog dog".
Follow-Up:
- How would you extend this solution to handle multi-character patterns or words?