256. Word Pattern
You get a pattern made of lowercase letters and a sentence s made of lowercase words separated by single spaces. Decide whether the sentence follows the pattern: there must be a one-to-one pairing between pattern letters and words such that walking the pattern letter by letter spells out the sentence word by word.
Two things have to hold at once:
- Every occurrence of a letter always stands for the same word.
- Two different letters never stand for the same word (the pairing is a bijection).
So abba matches dog cat cat dog, but neither dog cat cat fish (the second a changed words) nor dog dog dog dog (two letters claim dog).
The function receives pattern (a string) and s (a string of space-separated words) and returns a boolean — true if s follows pattern, false otherwise.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation: Pair a → dog and b → cat. Reading the pattern back gives dog cat cat dog, and no two letters share a word.
Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation: The first a is paired with dog, so the final a must also be dog — but the sentence ends in fish.
Constraints:
- 1 ≤ pattern.length ≤ 300
- pattern contains only lowercase English letters.
- 1 ≤ s.length ≤ 3000
- s consists of lowercase words separated by single spaces, with no leading or trailing space.
Hints:
Split the sentence into words first. If the word count differs from the pattern length, no pairing can exist — answer false immediately.
One map from letter → word catches a letter changing its word, but misses the reverse failure: `abba` vs `dog dog dog dog`, where two letters claim the same word.
Enforce both directions: keep letter → word and word → letter maps (or compare first-occurrence positions) and reject on any disagreement.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: pattern = "abba", s = "dog cat cat dog"
Expected output: true