Loading…

easyStringsLC #290Frequently asked

Word Pattern

Q: How do you solve Word Pattern using the Single Map of Index Signatures approach?

When to use it: When asked to use one container or to generalize: map each symbol (char or word) to the index of its first appearance and compare signatures. Rather than two maps for two directions, this approach encodes each sequence as the list of **first-occurrence indices** of its symbols, then checks the two encodings are identical. It mirrors the index-encoding trick from Isomorphic Strings. **Why it works.** Two sequences 'follow the same pattern' precisely when one can be relabeled into the other while preserving repetition structure. The first-occurrence index of each symbol is a label-independent fingerprint of that structure: for `"abba"`, `a` first appears at 0, `b` at 1, so the signature is `[0, 1, 1, 0]`. For the words `dog cat cat dog`, `dog` first appears at 0, `cat` at 1, giving the same `[0, 1, 1, 0]`. Equal signatures ⇔ bijection exists. Because we compare the *same index* contributed by both sides at each position, a mismatch in either direction surfaces as a divergent signature — no separate reverse map needed. **Why use first-occurrence and not last-occurrence.** Either works, but first-occurrence is the most natural canonical form: the i-th element of the signature answers *"where did this symbol debut?"* Two symbols that debut at the same step in both sequences must be 'the same role' in the pattern. If `pattern`'s symbol debuted at step 3 but the corresponding word debuted at step 1, the word was already used for a different pattern char — a conflict. **Why it's worth mentioning but not the default.** It's elegant and uses a single conceptual mechanism for both directions, which can impress. The downside is it's slightly more error-prone (you must use `putIfAbsent` / `setdefault` so only the *first* index is stored, and you still need the length guard). For most interviews the explicit two-map version reads more clearly, but offering this shows depth. Time complexity: O(n). Space complexity: O(n).

LCPractice

Arrays & Hashing · 25 of 83 · 9 min

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a **bijection** between a letter in pattern and a non-empty word in s.

Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

In plain English

We need a one-to-one correspondence between the single characters of `pattern` and the space-separated words of `s`, preserving order. The i-th pattern char must correspond to the i-th word, consistently, and the correspondence must be reversible — exactly the bijection condition from Isomorphic Strings, lifted from chars to whole words.

Examples

Example 1

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Note: a→dog, b→cat. The pattern abba demands dog cat cat dog, which matches exactly.

Example 2

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Note: a→dog, b→cat, b→cat, then the last a should be dog but the word is fish. char→word conflict.

Example 3

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Note: a→dog, then a→cat contradicts a→dog. char→word conflict on the second word.

Example 4

Input: pattern = "abba", s = "dog dog dog dog"
Output: false
Note: a→dog, then b→dog — but dog is already claimed by a. The reverse (word→char) map catches this; a single char→word map would wrongly pass.

Constraints

1 ≤ pattern.length ≤ 300
pattern contains only lowercase English letters
1 ≤ s.length ≤ 3000
s contains only lowercase English letters and single spaces between words
s does not contain leading or trailing spaces
Each word in s is separated by exactly one space

Clarifying questions4First question: Are words separated by exactly one space, with no leading/trailing spaces?Explore questions

Q1.Are words separated by exactly one space, with no leading/trailing spaces?
Per the constraints, yes. If the input could have irregular spacing I'd split and filter empty tokens, or use a regex split, to avoid spurious empty words.
Q2.Must the number of words equal the pattern length?
Yes — that's the first thing I check after splitting. 'abba' (4 chars) against 3 words can never match, so I return false immediately.
Q3.Can a word repeat, and must it always map to the same pattern char?
Yes. If 'dog' appears twice it must correspond to the same pattern char both times; otherwise the bijection breaks.
Q4.Are the pattern and words case-sensitive?
The constraints say lowercase only, so case isn't a concern here, but I'd confirm before assuming.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Split the sentence into words and require a bijection between pattern characters and words: each pattern char maps to exactly one word AND each word maps back to exactly one pattern char. Like Isomorphic Strings, one map is not enough — track both directions. Guard the length first: number of words must equal the pattern length. O(n) time, O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize this as the same bijection problem as Isomorphic Strings, just with words instead of characters — and whether you remember to verify the mapping in both directions.

Where candidates slip

Only mapping char→word (so 'abba' with 'dog dog dog dog' wrongly passes), or comparing lengths of the raw strings instead of pattern length vs word count.

How to stand out

Say 'this is Isomorphic Strings with words as tokens' immediately, handle the split-and-count guard explicitly, and mention the single-map-with-index-encoding alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Hash Maps — char↔word Bijection (Optimal)Optimal	`O(n)`	`O(n)`	The canonical answer. Open with 'this is Isomorphic Strings with words as the second alphabet'.	Read
2	Single Map of Index Signatures	`O(n)`	`O(n)`	When asked to use one container or to generalize: map each symbol (char or word) to the index of its first appearance and compare signatures.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSplit s into wordslen(pattern) == #words?NoYesExplore the full tree

char→word map on the failing dog-dog casepattern = "abba", s = "dog dog dog dog"

How to read it:Forward map looks fine until the reverse map rejects b→dog because dog already belongs to a.

Frame 1
i=0, a/dog
a unseen, dog unclaimed → a→dog, dog→a
a→ dog
Frame 2
i=1, b/dog
b unseen forward, BUT dog already claimed by a in reverse → false
a→ dog
Looked up b — not in map.

Just inserted / updatedLooking upMatch

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Two Hash Maps — char↔word Bijection (Optimal)

TimeO(n)SpaceO(n)

The canonical answer. Open with 'this is Isomorphic Strings with words as the second alphabet'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What does 'bijection' demand beyond 'every pattern char picks a word'? It also demands that no two pattern chars pick the SAME word. That reverse condition needs its own map.

2Hint 2Explore hint

Split s into words first. If the word count differs from the pattern length, return false before doing anything else.

3Hint 3Explore hint

Keep c2w (char→word) and w2c (word→char). For each pair, fail if either direction already disagrees; otherwise record both.

A · Core idea

After splitting the sentence into a list of words, the problem is identical in shape to Isomorphic Strings: we need a bijection between two sequences of equal length — here the pattern's characters and the sentence's words. We walk both sequences in lockstep and enforce consistency in both directions.

Why this is the same problem as Isomorphic Strings. In Isomorphic Strings the second alphabet was individual characters of t; here it is whole words. Nothing else changes. The bijection requirement — each pattern char maps to exactly one word and each word maps back to exactly one char — is structurally the same constraint. Recognizing this lets you reuse a battle-tested template instead of inventing logic under pressure. Saying that out loud signals pattern fluency to the interviewer.

Why both maps are mandatory. Consider pattern = "abba", s = "dog dog dog dog". A char→word map records a→dog, then at the b/dog pair b is unseen, so a forward-only check happily adds b→dog. But now two pattern chars (a and b) both point at dog, violating one-to-one. The reverse map w2c already contains dog→a, so when b tries to claim dog we detect that dog is taken and return false. The forward map catches char→word conflicts ("aaaa" vs "dog cat cat dog"); the reverse map catches word→char conflicts. You need both because a bijection has two halves.

Why the length guard comes first. Splitting "dog cat cat" yields three words; matching it against the four-character pattern "abba" is impossible. If you skip the guard and rely on zip, Python silently stops at the shorter sequence and might return true for a pattern that is genuinely longer. Comparing len(pattern) to the number of words after splitting closes that hole. Note: compare against the word count, never against len(s) — the raw string length is unrelated to the number of tokens.

Why check before write. As in every bijection scan, we verify both directions before inserting. If we inserted first, the new entry would trivially agree with itself and a conflict on that very step would be masked.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

pattern = "abba", s = "dog cat cat fish"

Hash-map state

i=0, a/dog

lookup a

ValueIndex / state

a→ dog

Continue scanning

new → a→dog

Final resultfalse

C · Code with teaching comments

solution.javaJava

Two Hash Maps — char↔word Bijection (Optimal) — optimal

4 teaching notes

1
public boolean wordPattern(String pattern, String s) {
2
    // Tokenize the sentence — the unit of mapping is a whole word.
3
    String[] words = s.split(" ");
4
    // Counts must match; compare against word count, not s.length().
5
    if (pattern.length() != words.length) return false;
6
    Map<Character, String> c2w = new HashMap<>();
7
    Map<String, Character> w2c = new HashMap<>();
8
    for (int i = 0; i < words.length; i++) {
9
        char c = pattern.charAt(i);
10
        String w = words[i];
11
        // char→word consistency. Use .equals for String comparison, never ==.
12
        if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
13
        // word→char consistency — the half a single map misses.
14
        if (w2c.containsKey(w) && w2c.get(w) != c) return false;
15
        c2w.put(c, w);
16
        w2c.put(w, c);
17
    }
18
    return true;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The unit of mapping is the token, not the letter. The single conceptual leap from Isomorphic Strings is 'split the sentence, then treat each word as one symbol'. Once tokenized, the bijection machinery is identical — which is exactly why interviewers pair these two problems: they test whether you see past surface differences to the shared structure.

ComplexityO(n) time, O(n) space — Splitting is O(n) over the sentence. The single pass over k pairs does O(L) work per comparison where L is word length, totaling O(n). Maps hold up to k distinct words → O(n) space (words can be long, so space scales with input, unlike the fixed-alphabet char case).

E · Edge cases and pitfalls7pattern = "a", s = "dog" — Single pair, both new, record a→dog → true.Explore edge cases

Edge cases handled

pattern = "a", s = "dog"Single pair, both new, record a→dog → true.
pattern = "ab", s = "dog dog"a→dog, then b/dog: dog claimed by a in w2c → false.
pattern = "abc", s = "b c a"Three distinct chars, three distinct words, all 1-to-1 → true (words happen to look like letters, irrelevant).

Pitfalls

Comparing pattern.length() to s.length() instead of words.length — those are unrelated.
Using == on Strings in Java instead of .equals — reference vs value comparison.
Only keeping a char→word map — passes 'abba' / 'dog dog dog dog' incorrectly.
Assuming clean spacing without confirming; irregular spaces produce empty tokens.

03.2

Approach 2 of 2

Single Map of Index Signatures

TimeO(n)SpaceO(n)

When asked to use one container or to generalize: map each symbol (char or word) to the index of its first appearance and compare signatures.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Two sequences follow the same pattern iff their first-occurrence index signatures are identical. 'abba' → [0,1,1,0]; 'dog cat cat dog' → [0,1,1,0]. Equal → match.

2Hint 2Explore hint

Use one dictionary that records, for each distinct symbol, the index where it first appeared. Build the signature for the pattern and for the words and compare element by element.

3Hint 3Explore hint

putIfAbsent each symbol's first index; if at step i the pattern's recorded first index differs from the words' recorded first index, return false.

A · Core idea

Rather than two maps for two directions, this approach encodes each sequence as the list of first-occurrence indices of its symbols, then checks the two encodings are identical. It mirrors the index-encoding trick from Isomorphic Strings.

Why it works. Two sequences 'follow the same pattern' precisely when one can be relabeled into the other while preserving repetition structure. The first-occurrence index of each symbol is a label-independent fingerprint of that structure: for "abba", a first appears at 0, b at 1, so the signature is [0, 1, 1, 0]. For the words dog cat cat dog, dog first appears at 0, cat at 1, giving the same [0, 1, 1, 0]. Equal signatures ⇔ bijection exists. Because we compare the same index contributed by both sides at each position, a mismatch in either direction surfaces as a divergent signature — no separate reverse map needed.

Why use first-occurrence and not last-occurrence. Either works, but first-occurrence is the most natural canonical form: the i-th element of the signature answers "where did this symbol debut?" Two symbols that debut at the same step in both sequences must be 'the same role' in the pattern. If pattern's symbol debuted at step 3 but the corresponding word debuted at step 1, the word was already used for a different pattern char — a conflict.

Why it's worth mentioning but not the default. It's elegant and uses a single conceptual mechanism for both directions, which can impress. The downside is it's slightly more error-prone (you must use putIfAbsent / setdefault so only the first index is stored, and you still need the length guard). For most interviews the explicit two-map version reads more clearly, but offering this shows depth.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

pattern = "abba", s = "dog cat cat dog"

i=0

first(a)=0, first(dog)=0 → equal

Statefp={a:0}, fw={dog:0}

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (pattern.length() != words.length) return false; Map<Character, Integer> fp = new HashMap<>(); Map<String, Integer> fw = new HashMap<>();Explore the full code

solution.javaJava

Single Map of Index Signatures — reference

3 teaching notes

1
public boolean wordPattern(String pattern, String s) {
2
    String[] words = s.split(" ");
3
    if (pattern.length() != words.length) return false;
4
    Map<Character, Integer> fp = new HashMap<>();
5
    Map<String, Integer> fw = new HashMap<>();
6
    for (int i = 0; i < words.length; i++) {
7
        char c = pattern.charAt(i);
8
        String w = words[i];
9
        // Store first index only; putIfAbsent returns the prior value (null if newly
10
        // inserted).
11
        Integer ip = fp.putIfAbsent(c, i);
12
        Integer iw = fw.putIfAbsent(w, i);
13
        // Resolve to the symbol's first-occurrence index.
14
        int firstP = (ip == null) ? i : ip;
15
        int firstW = (iw == null) ? i : iw;
16
        // Signatures diverge → not the same pattern.
17
        if (firstP != firstW) return false;
18
    }
19
    return true;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Pattern-following is invariance of repetition structure under relabeling. Encoding each sequence by 'first index of each symbol' collapses both the forward and reverse consistency into one signature comparison — the same canonical-form idea that powers Group Anagrams.

ComplexityO(n) time, O(n) space — One pass building both signatures with O(1) average map ops → O(n). Two maps holding up to k symbols → O(n) space.

E · Edge cases and pitfalls5pattern = "abba", s = "dog dog dog dog" — At i=1 first(b)=1 but first(dog)=0 → 1 != 0 → false.Explore edge cases

Edge cases handled

pattern = "abba", s = "dog dog dog dog"At i=1 first(b)=1 but first(dog)=0 → 1 != 0 → false.
pattern = "aaaa", s = "dog cat cat dog"At i=1 first(a)=0 but first(cat)=1 → 0 != 1 → false.

Pitfalls

Using put instead of putIfAbsent / setdefault — overwrites and stores last index, breaking the signature.
Skipping the length guard — zip truncates in Python.
Mixing int and Integer comparison carelessly in Java — unbox before ==.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (pattern.length() != words.length) return false; Map<Character, String> c2w = new HashMap<>(); Map<String, Character> w2c = new HashMap<>();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Single map, missing reverse direction

Without word→char, two pattern chars can claim the same word. On 'abba' / 'dog dog dog dog', b→dog is added even though dog already belongs to a.

Explore the code comparison

Don't write this

Map<Character,String> c2w = new HashMap<>();
for (int i = 0; i < words.length; i++) {
    char c = pattern.charAt(i);
    if (c2w.containsKey(c) && !c2w.get(c).equals(words[i])) return false;
    c2w.put(c, words[i]);
}
return true;

Write this instead

Map<Character,String> c2w = new HashMap<>();
Map<String,Character> w2c = new HashMap<>();
for (int i = 0; i < words.length; i++) {
    char c = pattern.charAt(i);
    String w = words[i];
    if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
    if (w2c.containsKey(w) && w2c.get(w) != c) return false;
    c2w.put(c, w);
    w2c.put(w, c);
}
return true;

Comparing the wrong lengths

pattern.length() counts characters; s.length() counts characters of the whole sentence including spaces. You must compare pattern length to the number of WORDS.

Explore the code comparison

Don't write this

if len(pattern) != len(s):
    return False

Write this instead

words = s.split(' ')
if len(pattern) != len(words):
    return False

String identity vs equality in Java

c2w.get(c) == w compares references. Two equal-content Strings can be different objects, so this can wrongly return false. Use .equals.

Explore the code comparison

Don't write this

if (c2w.containsKey(c) && c2w.get(c) != w) return false;

Write this instead

if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bijection between chars and words (two maps)

Code pattern to memorize

words = s.split(' ')
if len(pattern) != len(words): return False
for c, w in zip(pattern, words):
    if c in c2w and c2w[c] != w: return False
    if w in w2c and w2c[w] != c: return False
    c2w[c] = w; w2c[w] = c
return True

Rules to remember

1Split on spaces FIRST and compare counts — pattern="abba" vs words of length 3 is an instant false.
2Check both directions: char→word and word→char. pattern="abba", s="dog dog dog dog" must fail because b would map to dog which is already a's word.
3A word may be multiple characters — the unit is the whole word, not a letter. Don't iterate the sentence char by char.
4Use .split(' ') semantics carefully; leading/trailing/multiple spaces can create empty tokens — clarify input cleanliness.
5Check before writing so a fresh entry can't agree with itself and hide a conflict.

Use this pattern when

Mapping a short symbolic pattern onto a sequence of tokens / words
Any 'does this template consistently describe this sequence?' question
Tokens are multi-character but must translate one-to-one
You recognize it as Isomorphic Strings lifted from chars to words

Choose another pattern when

Only one direction matters → single map (rare; usually it's a true bijection)
Order is irrelevant → frequency comparison instead
Pattern can repeat words freely (many-to-one) → drop the reverse map
You must output the mapping, not a boolean → store and return the dict

Interview takeaway

Word Pattern is Isomorphic Strings with words as the second alphabet. The exact same two-map bijection check applies — split into tokens, verify both directions. The classic trap is forgetting the reverse map or forgetting the length guard after splitting.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBijection via two hash maps, tokenized to words. Recognise it as Isomorphic Strings whenever a short symbolic pattern must consistently and reversibly describe a sequence of tokens. The reverse map and the post-split length guard are the two things candidates forget.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Isomorphic Strings
The same bijection but between characters of two strings — Word Pattern is this lifted to words.
Word Pattern II
Coming soon
No spaces in s — you must backtrack over possible word boundaries while maintaining the bijection.
Find and Replace Pattern
Coming soon
Filter a word list by whether each word is isomorphic to the pattern — reuse the bijection check per word.
Group Anagrams
Canonical-form grouping — same 'normalize then compare' idea as the index-signature approach.

Same pattern

←

Text Justification

Continue · Next problem

Zigzag Conversion

easyStringsLC #290Frequently asked

Word Pattern

LCPractice

Arrays & Hashing · 25 of 83 · 9 min

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a **bijection** between a letter in pattern and a non-empty word in s.

Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

In plain English

Examples

Example 1

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Note: a→dog, b→cat. The pattern abba demands dog cat cat dog, which matches exactly.

Example 2

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Note: a→dog, b→cat, b→cat, then the last a should be dog but the word is fish. char→word conflict.

Example 3

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Note: a→dog, then a→cat contradicts a→dog. char→word conflict on the second word.

Example 4

Input: pattern = "abba", s = "dog dog dog dog"
Output: false
Note: a→dog, then b→dog — but dog is already claimed by a. The reverse (word→char) map catches this; a single char→word map would wrongly pass.

Constraints

1 ≤ pattern.length ≤ 300
pattern contains only lowercase English letters
1 ≤ s.length ≤ 3000
s contains only lowercase English letters and single spaces between words
s does not contain leading or trailing spaces
Each word in s is separated by exactly one space

Clarifying questions4First question: Are words separated by exactly one space, with no leading/trailing spaces?Explore questions

Q1.Are words separated by exactly one space, with no leading/trailing spaces?
Per the constraints, yes. If the input could have irregular spacing I'd split and filter empty tokens, or use a regex split, to avoid spurious empty words.
Q2.Must the number of words equal the pattern length?
Yes — that's the first thing I check after splitting. 'abba' (4 chars) against 3 words can never match, so I return false immediately.
Q3.Can a word repeat, and must it always map to the same pattern char?
Yes. If 'dog' appears twice it must correspond to the same pattern char both times; otherwise the bijection breaks.
Q4.Are the pattern and words case-sensitive?
The constraints say lowercase only, so case isn't a concern here, but I'd confirm before assuming.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize this as the same bijection problem as Isomorphic Strings, just with words instead of characters — and whether you remember to verify the mapping in both directions.

Where candidates slip

Only mapping char→word (so 'abba' with 'dog dog dog dog' wrongly passes), or comparing lengths of the raw strings instead of pattern length vs word count.

How to stand out

Say 'this is Isomorphic Strings with words as tokens' immediately, handle the split-and-count guard explicitly, and mention the single-map-with-index-encoding alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Hash Maps — char↔word Bijection (Optimal)Optimal	`O(n)`	`O(n)`	The canonical answer. Open with 'this is Isomorphic Strings with words as the second alphabet'.	Read
2	Single Map of Index Signatures	`O(n)`	`O(n)`	When asked to use one container or to generalize: map each symbol (char or word) to the index of its first appearance and compare signatures.	Read

char→word map on the failing dog-dog casepattern = "abba", s = "dog dog dog dog"

How to read it:Forward map looks fine until the reverse map rejects b→dog because dog already belongs to a.

Frame 1
i=0, a/dog
a unseen, dog unclaimed → a→dog, dog→a
a→ dog
Frame 2
i=1, b/dog
b unseen forward, BUT dog already claimed by a in reverse → false
a→ dog
Looked up b — not in map.

Just inserted / updatedLooking upMatch

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Two Hash Maps — char↔word Bijection (Optimal)

TimeO(n)SpaceO(n)

The canonical answer. Open with 'this is Isomorphic Strings with words as the second alphabet'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What does 'bijection' demand beyond 'every pattern char picks a word'? It also demands that no two pattern chars pick the SAME word. That reverse condition needs its own map.

2Hint 2Explore hint

Split s into words first. If the word count differs from the pattern length, return false before doing anything else.

3Hint 3Explore hint

Keep c2w (char→word) and w2c (word→char). For each pair, fail if either direction already disagrees; otherwise record both.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

pattern = "abba", s = "dog cat cat fish"

Hash-map state

i=0, a/dog

lookup a

ValueIndex / state

a→ dog

Continue scanning

new → a→dog

Final resultfalse

C · Code with teaching comments

solution.javaJava

Two Hash Maps — char↔word Bijection (Optimal) — optimal

4 teaching notes

1
public boolean wordPattern(String pattern, String s) {
2
    // Tokenize the sentence — the unit of mapping is a whole word.
3
    String[] words = s.split(" ");
4
    // Counts must match; compare against word count, not s.length().
5
    if (pattern.length() != words.length) return false;
6
    Map<Character, String> c2w = new HashMap<>();
7
    Map<String, Character> w2c = new HashMap<>();
8
    for (int i = 0; i < words.length; i++) {
9
        char c = pattern.charAt(i);
10
        String w = words[i];
11
        // char→word consistency. Use .equals for String comparison, never ==.
12
        if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
13
        // word→char consistency — the half a single map misses.
14
        if (w2c.containsKey(w) && w2c.get(w) != c) return false;
15
        c2w.put(c, w);
16
        w2c.put(w, c);
17
    }
18
    return true;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7pattern = "a", s = "dog" — Single pair, both new, record a→dog → true.Explore edge cases

Edge cases handled

pattern = "a", s = "dog"Single pair, both new, record a→dog → true.
pattern = "ab", s = "dog dog"a→dog, then b/dog: dog claimed by a in w2c → false.
pattern = "abc", s = "b c a"Three distinct chars, three distinct words, all 1-to-1 → true (words happen to look like letters, irrelevant).

Pitfalls

Comparing pattern.length() to s.length() instead of words.length — those are unrelated.
Using == on Strings in Java instead of .equals — reference vs value comparison.
Only keeping a char→word map — passes 'abba' / 'dog dog dog dog' incorrectly.
Assuming clean spacing without confirming; irregular spaces produce empty tokens.

03.2

Approach 2 of 2

Single Map of Index Signatures

TimeO(n)SpaceO(n)

When asked to use one container or to generalize: map each symbol (char or word) to the index of its first appearance and compare signatures.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Two sequences follow the same pattern iff their first-occurrence index signatures are identical. 'abba' → [0,1,1,0]; 'dog cat cat dog' → [0,1,1,0]. Equal → match.

2Hint 2Explore hint

Use one dictionary that records, for each distinct symbol, the index where it first appeared. Build the signature for the pattern and for the words and compare element by element.

3Hint 3Explore hint

putIfAbsent each symbol's first index; if at step i the pattern's recorded first index differs from the words' recorded first index, return false.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

pattern = "abba", s = "dog cat cat dog"

i=0

first(a)=0, first(dog)=0 → equal

Statefp={a:0}, fw={dog:0}

Final resulttrue

C · Code with teaching comments

solution.javaJava

Single Map of Index Signatures — reference

3 teaching notes

1
public boolean wordPattern(String pattern, String s) {
2
    String[] words = s.split(" ");
3
    if (pattern.length() != words.length) return false;
4
    Map<Character, Integer> fp = new HashMap<>();
5
    Map<String, Integer> fw = new HashMap<>();
6
    for (int i = 0; i < words.length; i++) {
7
        char c = pattern.charAt(i);
8
        String w = words[i];
9
        // Store first index only; putIfAbsent returns the prior value (null if newly
10
        // inserted).
11
        Integer ip = fp.putIfAbsent(c, i);
12
        Integer iw = fw.putIfAbsent(w, i);
13
        // Resolve to the symbol's first-occurrence index.
14
        int firstP = (ip == null) ? i : ip;
15
        int firstW = (iw == null) ? i : iw;
16
        // Signatures diverge → not the same pattern.
17
        if (firstP != firstW) return false;
18
    }
19
    return true;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — One pass building both signatures with O(1) average map ops → O(n). Two maps holding up to k symbols → O(n) space.

E · Edge cases and pitfalls5pattern = "abba", s = "dog dog dog dog" — At i=1 first(b)=1 but first(dog)=0 → 1 != 0 → false.Explore edge cases

Edge cases handled

pattern = "abba", s = "dog dog dog dog"At i=1 first(b)=1 but first(dog)=0 → 1 != 0 → false.
pattern = "aaaa", s = "dog cat cat dog"At i=1 first(a)=0 but first(cat)=1 → 0 != 1 → false.

Pitfalls

Using put instead of putIfAbsent / setdefault — overwrites and stores last index, breaking the signature.
Skipping the length guard — zip truncates in Python.
Mixing int and Integer comparison carelessly in Java — unbox before ==.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Single map, missing reverse direction

Without word→char, two pattern chars can claim the same word. On 'abba' / 'dog dog dog dog', b→dog is added even though dog already belongs to a.

Explore the code comparison

Don't write this

Map<Character,String> c2w = new HashMap<>();
for (int i = 0; i < words.length; i++) {
    char c = pattern.charAt(i);
    if (c2w.containsKey(c) && !c2w.get(c).equals(words[i])) return false;
    c2w.put(c, words[i]);
}
return true;

Write this instead

Map<Character,String> c2w = new HashMap<>();
Map<String,Character> w2c = new HashMap<>();
for (int i = 0; i < words.length; i++) {
    char c = pattern.charAt(i);
    String w = words[i];
    if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
    if (w2c.containsKey(w) && w2c.get(w) != c) return false;
    c2w.put(c, w);
    w2c.put(w, c);
}
return true;

Comparing the wrong lengths

pattern.length() counts characters; s.length() counts characters of the whole sentence including spaces. You must compare pattern length to the number of WORDS.

Explore the code comparison

Don't write this

if len(pattern) != len(s):
    return False

Write this instead

words = s.split(' ')
if len(pattern) != len(words):
    return False

String identity vs equality in Java

c2w.get(c) == w compares references. Two equal-content Strings can be different objects, so this can wrongly return false. Use .equals.

Explore the code comparison

Don't write this

if (c2w.containsKey(c) && c2w.get(c) != w) return false;

Write this instead

if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bijection between chars and words (two maps)

Code pattern to memorize

words = s.split(' ')
if len(pattern) != len(words): return False
for c, w in zip(pattern, words):
    if c in c2w and c2w[c] != w: return False
    if w in w2c and w2c[w] != c: return False
    c2w[c] = w; w2c[w] = c
return True

Rules to remember

1Split on spaces FIRST and compare counts — pattern="abba" vs words of length 3 is an instant false.
2Check both directions: char→word and word→char. pattern="abba", s="dog dog dog dog" must fail because b would map to dog which is already a's word.
3A word may be multiple characters — the unit is the whole word, not a letter. Don't iterate the sentence char by char.
4Use .split(' ') semantics carefully; leading/trailing/multiple spaces can create empty tokens — clarify input cleanliness.
5Check before writing so a fresh entry can't agree with itself and hide a conflict.

Use this pattern when

Mapping a short symbolic pattern onto a sequence of tokens / words
Any 'does this template consistently describe this sequence?' question
Tokens are multi-character but must translate one-to-one
You recognize it as Isomorphic Strings lifted from chars to words

Choose another pattern when

Only one direction matters → single map (rare; usually it's a true bijection)
Order is irrelevant → frequency comparison instead
Pattern can repeat words freely (many-to-one) → drop the reverse map
You must output the mapping, not a boolean → store and return the dict

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Isomorphic Strings
The same bijection but between characters of two strings — Word Pattern is this lifted to words.
Word Pattern II
Coming soon
No spaces in s — you must backtrack over possible word boundaries while maintaining the bijection.
Find and Replace Pattern
Coming soon
Filter a word list by whether each word is isomorphic to the pattern — reuse the bijection check per word.
Group Anagrams
Canonical-form grouping — same 'normalize then compare' idea as the index-signature approach.

Same pattern

←

Text Justification

Continue · Next problem

Zigzag Conversion