Word Pattern Algorithm

Given a pattern like "abba" and a string like "dog cat cat dog", check if the string follows the pattern. Each letter maps to exactly one word, and each word maps to exactly one letter. It's a bijection — a one-to-one, two-way mapping.

pattern = "abba", s = "dog cat cat dog" → true
pattern = "abba", s = "dog cat cat fish" → false
pattern = "abba", s = "dog dog dog dog" → false (a and b can't both map to "dog")

The intuition

You need two maps: one from pattern letters to words, one from words back to pattern letters. If a letter is already mapped to a different word, fail. If a word is already mapped to a different letter, fail. Both directions must agree.

Most people only check one direction and miss cases like "abba" → "dog dog dog dog".

var wordPattern = function(pattern, s) {
    const words = s.trim().split(' ');

    if (pattern.length !== words.length) return false;

    const letterToWord = new Map();
    const wordToLetter = new Map();

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

        if (letterToWord.has(letter) && letterToWord.get(letter) !== word) return false;
        if (wordToLetter.has(word) && wordToLetter.get(word) !== letter) return false;

        letterToWord.set(letter, word);
        wordToLetter.set(word, letter);
    }

    return true;
};

Complexity

• Time: O(n) where n is the number of words/pattern characters.
• Space: O(n) for the two maps.

Why two maps?

A single map from letters to words can't catch the case where two different letters map to the same word. The reverse map enforces the bijection. This two-map pattern comes up any time you need to verify a one-to-one correspondence — isomorphic strings, cipher validation, symbol mapping.