#290

Easy

LeetCode Problem Workspace

Word Pattern

Solve Word Pattern by checking a one-to-one mapping between pattern letters and words using hash tables after splitting the string.

hash table string

Problem Statement

Word Pattern asks whether a pattern string and a space-separated string of words match under a strict one-to-one rule. Each character in the pattern must always map to the same non-empty word everywhere it appears, so repeated letters must repeat the same word at the corresponding positions.

The failure case that matters is collision in either direction. If one letter points to two different words, or two different letters point to the same word, the pattern is broken. For example, pattern = "abba" with s = "dog cat cat dog" works because a maps to dog and b maps to cat, while pattern = "abba" with s = "dog cat cat fish" fails on the last word.

Examples

Example 1

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

Output: true

The bijection can be established as:

Example 2

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

Output: false

Example details omitted.

Example 3

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

Output: false

Example details omitted.

Constraints

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Solution Approach

Split the string and reject mismatched lengths first

Start by splitting s on spaces into a word array. If the number of words does not equal pattern.length, return false immediately because Word Pattern requires a full position-by-position match, not a partial mapping.

Track the character-to-word mapping

Use a hash table from pattern character to word. As you scan each index, if the character has been seen before, its stored word must equal the current word. If it does not, you found the classic repeat-letter mismatch that makes Word Pattern false.

Enforce the reverse direction to keep the mapping bijective

Also track word-to-character, or keep a set of already assigned words while checking new characters. This prevents two different pattern letters from claiming the same word, which is the other key failure mode in Word Pattern and the reason a single forward map alone is incomplete.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let n be the number of characters in s and m be pattern.length. Splitting the string costs O(n), and the validation pass over the words costs O(m), so the total time is O(n + m). The extra space is O(m) for the hash tables in the worst case when each pattern letter and word pairing is distinct.

What Interviewers Usually Probe

They want you to say "bijection" or explicitly explain why checking only character-to-word mapping is insufficient.
They expect an early length check after splitting, because Word Pattern requires every pattern position to match one word.
They may probe whether two different letters can map to the same word, which reveals whether you handled the reverse mapping.

Common Pitfalls or Variants

Common pitfalls

Using only one hash map and accidentally accepting cases where two pattern letters share one word.
Forgetting to compare word count against pattern length before building mappings.
Treating this like substring matching instead of exact token-by-token word matching separated by spaces.

Follow-up variants

Return the actual mapping for Word Pattern instead of only true or false.
Handle an input where words are streamed one by one instead of pre-splitting the full string.
Generalize the same bijection check to pattern tokens and sentence tokens beyond single characters and lowercase words.

FAQ

What is the main idea behind Word Pattern?

The main idea is enforcing a bijection between pattern letters and words. A valid solution must make repeated letters reuse the same word and must also block two different letters from mapping to one word.

Why is one hash map not enough for Word Pattern?

A single character-to-word map catches when one letter changes words, but it misses word reuse by a different letter. You need the reverse check as well, either with a second map or with a used-word structure.

What should I check before building mappings?

First split s into words and compare the word count with pattern.length. If they differ, Word Pattern cannot be valid because the mapping must cover every position exactly once.

Is Word Pattern a hash table problem or a string problem?

It is both. The string part is tokenizing s into words correctly, and the hash table part is enforcing the one-to-one mapping without collisions.

What makes pattern = "aaaa" and s = "dog cat cat dog" false?

The letter a appears at every position, so it must map to one single word everywhere. Seeing dog first and cat later breaks that consistency immediately, so the answer is false.

terminal

Solution

Solution 1: Hash Table

First, we split the string $s$ into a word array $ws$ with spaces. If the length of $pattern$ and $ws$ is not equal, return `false` directly. Otherwise, we use two hash tables $d_1$ and $d_2$ to record the correspondence between each character and word in $pattern$ and $ws$.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        ws = s.split()
        if len(pattern) != len(ws):
            return False
        d1 = {}
        d2 = {}
        for a, b in zip(pattern, ws):
            if (a in d1 and d1[a] != b) or (b in d2 and d2[b] != a):
                return False
            d1[a] = b
            d2[b] = a
        return True

Solution 2

#### TypeScript

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        ws = s.split()
        if len(pattern) != len(ws):
            return False
        d1 = {}
        d2 = {}
        for a, b in zip(pattern, ws):
            if (a in d1 and d1[a] != b) or (b in d2 and d2[b] != a):
                return False
            d1[a] = b
            d2[b] = a
        return True

Continue Practicing

#299 bulls and cows #336 palindrome pairs #242 valid anagram