LeetCode Challenge: 290. Word Pattern - JavaScript Solution 🚀

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

1. Split Words:

   • Split the string s into an array of words using split(" ").

2. Check Lengths:

   • If the length of pattern does not match the number of words in s, return false.

3. Use Two Maps:

   • Map each character in pattern to a word in s.
   • Map each word in s back to a character in pattern.

4. Validate Mappings:

   • If a character or word conflicts with an existing mapping, return false.

5. 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

1. Explain Two Maps:

   • Highlight how mapping both char -> word and word -> char ensures consistency.

2. Discuss Edge Cases:

   • pattern and s lengths differ: pattern = "abba", s = "dog cat".
   • Duplicate mappings: pattern = "ab", s = "dog dog".

3. Follow-Up:

   • How would you extend this solution to handle multi-character patterns or words?

---

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Isomorphic Strings - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!