TL;DR
Two hash maps enforcing a bijection letter↔word — O(n + m) time, O(n + m) space (n letters, m total characters of s).
Approach 1 — Brute force (pairwise consistency)
A sentence follows the pattern iff for every pair of positions i, j: the letters match exactly when the words match. Check all pairs.
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split()
if len(pattern) != len(words):
return False
n = len(pattern)
for i in range(n):
for j in range(i + 1, n):
same_letter = pattern[i] == pattern[j]
same_word = words[i] == words[j]
if same_letter != same_word:
return False
return True
Complexity: O(n² · L) time (L = max word length), O(n) space.
At n ≤ 300 this passes easily — the constraints don’t kill it — but it re-derives the same facts O(n) times each; the hash-map version reads each position once, which is what scales.
Approach 2 — Two hash maps
The insight: a bijection is two functions that agree — letter → word and word → letter. Maintain both maps while scanning the pairs; the moment either map already holds a different partner for the current letter or word, the correspondence is broken.
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split()
if len(pattern) != len(words):
return False
letter_to_word: dict[str, str] = {}
word_to_letter: dict[str, str] = {}
for ch, w in zip(pattern, words):
if ch in letter_to_word and letter_to_word[ch] != w:
return False
if w in word_to_letter and word_to_letter[w] != ch:
return False
letter_to_word[ch] = w
word_to_letter[w] = ch
return True
Walkthrough on pattern = "abba", s = "dog dog dog dog":
- Pair
('a', "dog"): both maps empty → record a→dog, dog→a.
- Pair
('b', "dog"): b is new, but word_to_letter says “dog” already belongs to a ≠ b → return False.
And on s = "dog cat cat dog": pairs (a,dog), (b,cat), (b,cat) — consistent with existing entries — and (a,dog) again → True.
Complexity: O(n + m) time (split plus one pass; word comparisons total O(m)), O(n + m) space.
Approach 3 — First-occurrence fingerprint
The insight: two sequences are relabelings of each other iff each position’s first occurrence index matches. “abba” fingerprints as (0, 1, 1, 0), and so does “dog cat cat dog” — comparing fingerprints checks the bijection without storing an explicit mapping.
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split()
if len(pattern) != len(words):
return False
first_p = {}
first_w = {}
for i, (ch, w) in enumerate(zip(pattern, words)):
if first_p.setdefault(ch, i) != first_w.setdefault(w, i):
return False
return True
Walkthrough on pattern = "abba", s = "dog cat cat fish":
- i=0:
a and “dog” both first seen at 0 → 0 == 0.
- i=1:
b and “cat” both first seen at 1 → 1 == 1.
- i=2:
b first seen at 1, “cat” first seen at 1 → 1 == 1.
- i=3:
a first seen at 0, but “fish” first seen at 3 → 0 != 3 → False.
Complexity: O(n + m) time, O(n + m) space — same as Approach 2, just a slicker encoding of the same bijection test.
Common pitfalls
- Keeping only the letter → word map:
"abba" vs "dog dog dog dog" sails through because each letter is individually consistent — the reverse map (or fingerprint) is what catches two letters claiming one word.
- Forgetting the length check:
"aaa" vs "dog dog" must be False before any mapping logic runs (and zip would silently hide the mismatch).
- Comparing
len(set(pattern)) == len(set(words)) as a shortcut — necessary but not sufficient; positions must align, not just cardinalities.
Pattern takeaway
“Consistent relabeling” problems (this one, Isomorphic Strings) always need the constraint enforced in both directions — either two hash maps checked in lockstep, or the first-occurrence-index fingerprint that encodes both at once. A single forward map is the classic trap.