290. Word Pattern

Problem¶

Given a pattern like "abba" and a space-separated string like "dog cat cat dog", return True iff there is a one-to-one mapping between pattern letters and words.

Example:

pattern = "abba"
s       = "dog cat cat dog"
pairs   = a->dog, b->cat
answer  = True

Key trick¶

Check both directions of the mapping.

letter -> word must stay consistent
word -> letter must also stay consistent

Without the reverse check, two letters could incorrectly map to the same word.

Trap¶

Common mistakes:

Only storing letter -> word and forgetting bijection.
Forgetting to first check that number of letters equals number of words.
Using if mapping.get(ch) style checks that depend on truthiness instead of key existence.
Repeatedly using word in mapping.values(), which is less clean and turns lookup into linear time.

Why is it interesting?¶

It looks like simple string parsing, but the real idea is enforcing a bijection.

It is a small hash map problem that tests:

modeling constraints correctly
edge cases
clean dictionary usage

Python solution¶

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()

        # Full match requires same number of items.
        if len(pattern) != len(words):
            return False

        char_to_word = {}
        word_to_char = {}

        for ch, word in zip(pattern, words):
            # If either side already exists, both must match.
            if ch in char_to_word:
                if char_to_word[ch] != word:
                    return False
            elif word in word_to_char:
                return False
            else:
                char_to_word[ch] = word
                word_to_char[word] = ch

        return True

    def wordPattern_2(self, pattern: str, s: str) -> bool:
        words = s.split()
        return (
            len(pattern) == len(words)
            and len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words)))
        )

Comment on my solution¶

Your solution is correct on the main idea, but a few things should be improved.

Good:
- You checked length first.
- You enforced uniqueness, so you did handle bijection.
Issues:
- map shadows Python's built-in map.
- ch_word = map.get(ch, False) is unused.
- if map.get(ch, False) is a fragile pattern; use if ch in mapping.
- word in map.values() is \(O(n)\) each time, so the loop can become \(O(n^2)\).

A cleaner interview version uses two dictionaries and explicit membership checks.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        map = {}
        words = s.split()
        if len(pattern) != len(words):
            return False
        for ch,word in zip(pattern, words):
            ch_word = map.get(ch, False)
            if map.get(ch, False):
                if map[ch] != word:
                    return False
            else:
                if word in map.values():
                    return False
                else:
                    map[ch] = word
        return True


# Written after reading AI comments
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        ch_to_word = {}
        word_to_ch = {}
        words = s.split()
        if len(pattern) != len(words):
            return False
        for ch,word in zip(pattern, words):
            if ch in ch_to_word:
                if ch_to_word[ch] != word:
                    return False
            else:
                if word in word_to_ch:
                    return False
                else:
                    ch_to_word[ch] = word
                    word_to_ch[word] = ch
        return True