DEV Community

Cover image for LeetCode Challenge: 290. Word Pattern - JavaScript Solution ๐Ÿš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

3 1 1 1 1

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".
Enter fullscreen mode Exit fullscreen mode

Example 2

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

Example 3

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

๐Ÿ† 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;
};
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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"
Dry Run

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! ๐Ÿš€


Study

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (2)

Collapse
 
rahulgithubweb profile image
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!

๐Ÿ‘‹ Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay