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 if and only if, for every pair of positions i, j, the letters are equal exactly when the words are equal. Check all pairs.
def wordPattern(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, but it re-checks the same relationships O(n) times. The hash-map version reads each position once.
Approach 2 — Two hash maps
A bijection is two functions that agree: letter → word and word → letter. Maintain both maps while scanning the pairs. If either map already holds a different partner for the current letter or word, the correspondence is broken.
def wordPattern(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
Two sequences are relabelings of each other if and only if 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.
def wordPattern(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, the same as Approach 2 with a more compact encoding of the same bijection test.
Common pitfalls
- Keeping only the letter → word map:
"abba" vs "dog dog dog dog" passes 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, since zip would otherwise silently truncate to the shorter sequence and hide the mismatch.
- Comparing
len(set(pattern)) == len(set(words)) as a shortcut: necessary but not sufficient, because positions must align, not just cardinalities.
Pattern takeaway
“Consistent relabeling” problems (this one, Isomorphic Strings) 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 common mistake.