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

Sentry image

See why 4M developers consider Sentry, β€œnot bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

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!

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay