Word Pattern — Two-Way HashMap Bijection at the Word Level

Problem Statement#

Given a pattern string and a string s, return true if s follows the same pattern. Each character in pattern must map to exactly one word in s, and vice versa.

Constraints:

• 1 <= pattern.length <= 300
• pattern is lowercase English letters.
• 1 <= s.length <= 3000
• s contains lowercase English words separated by single spaces.

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

Input:  pattern = "abba", s = "dog cat cat fish"
Output: false

Why This Problem Matters#

LeetCode 290 Word Pattern is the natural extension of Isomorphic Strings from characters to words. Google, Amazon, Microsoft, and Meta phone screens use it to test whether a candidate generalizes a hashmap interview pattern. The interview signal is the two-way bijection: pattern character to word and word to pattern character.

The same bijection idea drives schema mapping verification, query-template matching, and cipher correctness in production. Hash table FAANG fluency means seeing past the cosmetic difference (single chars versus whole words) and reusing the pattern.

The trap: candidates often forget to verify lengths match before walking the inputs, or they use a single map and fail on cases like pattern = "ab", s = "dog dog".

The Core Insight#

Split s into a list of words. If len(pattern) != len(words) return false. Walk both in lockstep maintaining two HashMaps:

1. char_to_word[c] must always equal the current word.
2. word_to_char[w] must always equal the current pattern character.

Any conflict returns false. The pattern is exactly Isomorphic Strings with a different alphabet.

Visual Dry Run#

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

Return true.

Solution (Optimal)#

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False
        c_to_w: dict[str, str] = {}
        w_to_c: dict[str, str] = {}
        for c, w in zip(pattern, words):
            if c_to_w.get(c, w) != w:
                return False
            if w_to_c.get(w, c) != c:
                return False
            c_to_w[c] = w
            w_to_c[w] = c
        return True

var wordPattern = function(pattern, s) {
    const words = s.split(' ');
    if (pattern.length !== words.length) return false;
    const cToW = new Map();
    const wToC = new Map();
    for (let i = 0; i < pattern.length; i++) {
        const c = pattern[i], w = words[i];
        if (cToW.has(c) && cToW.get(c) !== w) return false;
        if (wToC.has(w) && wToC.get(w) !== c) return false;
        cToW.set(c, w);
        wToC.set(w, c);
    }
    return true;
};

Time: O(n + m) where n is pattern.length and m is total characters in s. Space: O(k) for the two HashMaps where k is the number of distinct pattern chars.

Common Mistakes#

• Skipping the length check. pattern = "abc", s = "dog cat" should return false immediately.
• Using only one HashMap. Misses pattern = "ab", s = "dog dog" where two pattern chars map to the same word.
• Splitting s with the wrong delimiter or trimming whitespace inconsistently.
• Pre-populating the maps before iteration. Breaks the position-consistent mapping invariant.
• Treating words case-insensitively when the problem says lowercase.

Interview Tips#

• State this as Isomorphic Strings on words. Interviewers like seeing pattern reuse.
• Always validate the length match before building the maps.
• For production hardening, mention sanitizing input (trim, lowercase) only when the problem allows.
• Mention zip(pattern, words) for elegant lockstep iteration in Python.

Follow-up Questions#

• What if s words are separated by arbitrary whitespace? (Hint: split() with no args collapses runs of whitespace.)
• What if you need to support multi-character pattern tokens? (Hint: tokenize pattern first.)
• How do you support a streaming variant where words arrive one at a time? (Hint: maintain both maps and validate as you go.)
• Generalize to Word Pattern II (LC 291). (Hint: backtracking with memoization.)
• What if the alphabet is Unicode? (Hint: HashMap handles arbitrary keys.)

Key Takeaways#

• LeetCode 290 Word Pattern is Isomorphic Strings lifted to whole words.
• Always check len(pattern) == len(words) first.
• Maintain two HashMaps: pattern char to word and word to pattern char.
• A single-direction map fails on inputs where two pattern chars map to the same word.
• Split s once with split() and zip with the pattern for clean iteration.
• Time is O(n + m); space is O(k) for the bijection maps.
• The bijection pattern recurs in cipher validation and schema mapping.