LeetCode 290: Word Pattern

Problem Restatement

We are given two strings:

pattern
s

pattern contains letters.

s contains words separated by spaces.

We need to check whether s follows the same pattern.

“Follows the same pattern” means there must be a bijection between pattern letters and words. In other words, each pattern letter maps to exactly one word, and each word maps back to exactly one pattern letter.

For example:

pattern = "abba"
s = "dog cat cat dog"

This is valid because:

The mapping is consistent in both directions.

Input and Output

Function shape:

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

Examples

For:

pattern = "abba"
s = "dog cat cat dog"

The result is:

True

because a always maps to "dog" and b always maps to "cat".

For:

pattern = "abba"
s = "dog cat cat fish"

The result is:

False

because a maps to "dog" at first, but the last a would need to map to "fish".

For:

pattern = "aaaa"
s = "dog cat cat dog"

The result is:

False

because one pattern letter cannot map to multiple different words.

For:

pattern = "abba"
s = "dog dog dog dog"

The result is:

False

because two different pattern letters, a and b, cannot both map to "dog".

First Thought: One Hash Map

A first idea is to map each pattern letter to a word.

For example:

a -> dog
b -> cat

Then, while scanning the input, if we see the same pattern letter again, it must map to the same word.

Code idea:

char_to_word = {}

This catches cases like:

pattern = "abba"
s = "dog cat cat fish"

because a first maps to "dog", then later tries to map to "fish".

But one map alone misses the reverse conflict.

For example:

pattern = "abba"
s = "dog dog dog dog"

A map from character to word can store:

a -> dog
b -> dog

But this is invalid because different pattern letters cannot map to the same word.

So we need to check both directions.

Key Insight

A bijection needs two constraints:

So we keep two hash maps:

char_to_word = {}
word_to_char = {}

For each pair (char, word):

1. If char already maps to another word, return False.
2. If word already maps to another char, return False.
3. Otherwise, record both mappings.

Algorithm

Split s into words:

words = s.split()

If the number of words differs from the number of pattern letters, return False.

Then scan both lists together.

For each pair:

char = pattern[i]
word = words[i]

Check the forward map:

if char in char_to_word and char_to_word[char] != word:
    return False

Check the reverse map:

if word in word_to_char and word_to_char[word] != char:
    return False

If both checks pass, store:

char_to_word[char] = word
word_to_char[word] = char

If the loop finishes, return True.

Correctness

The algorithm rejects exactly the cases that violate the required bijection.

If a pattern letter appears again with a different word, the forward map detects the conflict. This prevents one letter from mapping to multiple words.

If a word appears again with a different pattern letter, the reverse map detects the conflict. This prevents multiple letters from mapping to the same word.

If neither conflict occurs for every pair, then every pattern letter has one consistent word, and every word has one consistent pattern letter.

The length check ensures that every pattern letter is paired with exactly one word and no extra word remains unmatched.

Therefore the algorithm returns True exactly when s follows pattern.

Complexity

Let:

n = len(pattern)
m = len(s)

Implementation

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

        if len(pattern) != len(words):
            return False

        char_to_word = {}
        word_to_char = {}

        for char, word in zip(pattern, words):
            if char in char_to_word and char_to_word[char] != word:
                return False

            if word in word_to_char and word_to_char[word] != char:
                return False

            char_to_word[char] = word
            word_to_char[word] = char

        return True

Code Explanation

We first split the sentence into words:

words = s.split()

Then we check whether the counts match:

if len(pattern) != len(words):
    return False

A full match requires one word for every pattern letter.

The first map stores character-to-word relationships:

char_to_word = {}

The second map stores word-to-character relationships:

word_to_char = {}

For each pair:

for char, word in zip(pattern, words):

we check whether either direction conflicts with an earlier mapping.

If a conflict exists, the pattern fails immediately.

If no conflict exists, we record both mappings:

char_to_word[char] = word
word_to_char[word] = char

After all pairs pass, the string follows the pattern:

return True

Testing

def test_word_pattern():
    s = Solution()

    assert s.wordPattern("abba", "dog cat cat dog") is True
    assert s.wordPattern("abba", "dog cat cat fish") is False
    assert s.wordPattern("aaaa", "dog cat cat dog") is False
    assert s.wordPattern("abba", "dog dog dog dog") is False
    assert s.wordPattern("abc", "dog cat fish") is True
    assert s.wordPattern("abc", "dog cat") is False

    print("all tests passed")

test_word_pattern()

Test meaning: