Word Pattern
Last Updated: March 29, 2026
Understanding the Problem
We're given a pattern like "abba" and a sentence like "dog cat cat dog". The question is whether there's a one-to-one correspondence between letters in the pattern and words in the sentence. 'a' always maps to the same word, 'b' always maps to the same word, and no two different letters map to the same word.
The tricky part is that the mapping must be bijective, meaning it goes both ways. It's not enough for each letter to consistently map to the same word. We also need each word to consistently map to the same letter. For example, pattern "ab" and string "dog dog" should return false because both 'a' and 'b' would map to "dog", violating the bijection.
So the key observation is: we need to track two mappings simultaneously. One from characters to words, and another from words to characters. If either mapping is violated, the answer is false.
Key Constraints:
1 <= pattern.length <= 300-- The pattern is very small. Even O(n^2) would be fine, but O(n) is natural here.1 <= s.length <= 3000-- The string is also small. No need to worry about performance at all.patterncontains only lowercase English letters -- At most 26 distinct characters. A fixed-size array could work for the char-to-word mapping.- Words are separated by single spaces with no leading/trailing spaces -- Splitting on space is straightforward, no edge cases with whitespace.
Approach 1: Two Hash Maps (Bijection Check)
Intuition
The most natural approach: walk through the pattern and words in parallel, maintaining a mapping in both directions.
When we see a pattern character and a word together for the first time, we create a bidirectional mapping. If we see them again, we verify the existing mapping still holds. If a character was previously mapped to a different word, or a word was previously mapped to a different character, the bijection is broken.
Why two maps? Because a single map only enforces one direction. If we only track char-to-word, pattern "ab" with "dog dog" would incorrectly pass: 'a' -> "dog" is fine, and 'b' -> "dog" doesn't conflict with any existing mapping in a char-to-word map. But it violates the bijection because "dog" is now mapped to two different characters. The word-to-char map catches this.
A bijection means every element in one set maps to exactly one element in the other set, and vice versa. By maintaining two hash maps, we're explicitly enforcing both directions of this bijection. The charToWord map ensures each character consistently maps to the same word. The wordToChar map ensures each word consistently maps to the same character. Together, they guarantee the one-to-one correspondence the problem requires.
Algorithm
- Split the string
sinto an array of words. - If the number of words doesn't equal the length of
pattern, returnfalse. - Create two hash maps:
charToWord(character -> string) andwordToChar(string -> character). - For each index
i, get the current pattern character and the current word. - If the character already has a mapping in
charToWord, check that it maps to the current word. If not, returnfalse. - If the word already has a mapping in
wordToChar, check that it maps to the current character. If not, returnfalse. - If neither mapping exists, create both mappings.
- If we get through all positions without conflict, return
true.
Example Walkthrough
Code
- Time Complexity: O(n + m). Where n is the length of the pattern and m is the length of string s. Splitting the string takes O(m), and the main loop iterates n times with O(1) hash map operations per iteration.
- Space Complexity: O(n + m). The two hash maps store at most n entries each. The words array stores n words with total characters summing to at most m.
This approach works well and directly models the bijection. But what if instead of tracking explicit mappings, we just encoded the structure of each sequence and compared the encodings directly?
Approach 2: Index Mapping (Single-Pass Structure Comparison)
Intuition
Two sequences follow the same pattern if and only if they have the same "first occurrence" structure. Consider pattern "abba": the first occurrence indices are [0, 1, 1, 0], because 'a' first appears at index 0, 'b' first appears at index 1, 'b' was already seen at index 1, and 'a' was already seen at index 0. If the words "dog cat cat dog" produce the same structure [0, 1, 1, 0], the pattern matches.
This approach avoids the explicit bijection check entirely. Instead of asking "does the mapping hold in both directions?", we ask "do both sequences have the same structural fingerprint?"
Two sequences follow the same pattern when they have the same structure of repetitions. The first-occurrence index captures this structure perfectly. If 'a' first appears at index 0 and reappears at index 3, then the corresponding word must also first appear at index 0 and reappear at index 3. By comparing first-occurrence indices at each position, we're comparing the structural fingerprints of both sequences. This implicitly enforces the bijection without needing two separate maps.
Algorithm
- Split
sinto words. If the count doesn't match pattern length, returnfalse. - For each position, record the first occurrence index of the pattern character and the first occurrence index of the word.
- If at any position the first-occurrence indices differ between the pattern and the words, return
false. - If all positions match, return
true.
Example Walkthrough
Code
- Time Complexity: O(n + m). Same as Approach 1. Splitting takes O(m), the main loop is O(n) with O(1) hash map operations.
- Space Complexity: O(n + m). Two hash maps storing at most n entries each, plus the words array.