Word Pattern
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.
This means we need to track two mappings at once: 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 <= 300and1 <= s.length <= 3000. Both inputs are small, so an O(n + m) single pass is comfortable and there is no pressure to micro-optimize.patterncontains only lowercase English letters, so there are at most 26 distinct characters. A fixed-size 26-entry array could replace the char-to-word hash map if desired.- Words are separated by single spaces with no leading or trailing spaces, so splitting on a single space yields the words directly with no empty tokens to handle.
Approach 1: Two Hash Maps (Bijection Check)
Intuition
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 and not one? A single map only enforces one direction. If we track only char-to-word, pattern "ab" with "dog dog" passes incorrectly: 'a' -> "dog" is fine, and 'b' -> "dog" creates no conflict in a char-to-word map. But the bijection is violated because "dog" is now mapped to two different characters. The word-to-char map catches exactly this case: when 'b' arrives, "dog" already maps to 'a', so the mismatch fails the check. Each map guards one direction of the correspondence, and the problem requires both.
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 directly models the bijection with two explicit maps. The next approach reaches the same answer differently: instead of storing what each character and word map to, it encodes the repetition structure of each sequence and compares those structures position by position.
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. For pattern "abba", the first-occurrence indices are [0, 1, 1, 0]: 'a' first appears at index 0, 'b' first appears at index 1, the second 'b' was already seen at index 1, and the second 'a' was already seen at index 0. If "dog cat cat dog" produces the same sequence [0, 1, 1, 0], the pattern matches.
This replaces the explicit bijection check with a single structural comparison. At each position we compare the first-occurrence index of the pattern character against the first-occurrence index of the word, and they must agree.
The first-occurrence index at position i is the same for the character and the word exactly when both are "new" together or both are "repeats of the same earlier position" together. If the character is new at i (its first index is i) but the word repeats from an earlier position j < i, the indices differ and we reject. This rules out two characters mapping to one word and one character mapping to two words at the same time, so a single index comparison enforces the bijection in both directions without 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.