How do you approach Word Pattern?

Split s into words first - the word count must equal the pattern length.

What is the time complexity of Word Pattern?

Time complexity: O(n + m) - one pass over the pattern and the words. Space complexity: O(n) - the two maps.

What are common mistakes on Word Pattern?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

Sitelet https://gitgood.dev/coding/word-pattern

gitGood.dev

← Back to problems

Word Pattern

EasyData Structures

Description

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match: there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

Example 1

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

Output: true

Explanation: 'a' maps to "dog" and 'b' maps to "cat".

Example 2

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

Output: false

Example 3

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

Output: false

Constraints

- 1 <= pattern.length <= 300 - pattern contains only lowercase 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.

Word Pattern: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 7 test cases (4 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

Split s into words first - the word count must equal the pattern length.
A single map from letter to word is not enough: two different letters could map to the same word.
Keep two maps (letter -> word and word -> letter) and verify both directions on every position.

The optimal approach

Show the approach: Two Hash Maps (Bijection Check)

Split `s` into words and immediately fail if the count differs from the pattern length. Then walk both sequences in lockstep with two maps: letter-to-word and word-to-letter. At each position, if either map already has a conflicting entry, return false; otherwise record the pairing.

Time: O(n + m) - one pass over the pattern and the words
Space: O(n) - the two maps

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.

← Back to problems

Word Pattern

EasyData Structures

Description

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match: there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

Example 1

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

Output: true

Explanation: 'a' maps to "dog" and 'b' maps to "cat".

Example 2

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

Output: false

Example 3

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

Output: false

Constraints

Word Pattern: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 7 test cases (4 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

Split s into words first - the word count must equal the pattern length.
A single map from letter to word is not enough: two different letters could map to the same word.
Keep two maps (letter -> word and word -> letter) and verify both directions on every position.

The optimal approach

Show the approach: Two Hash Maps (Bijection Check)

Time: O(n + m) - one pass over the pattern and the words
Space: O(n) - the two maps

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.