Log inSign up
easyleetcodeNot Started

Word Pattern

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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.

- Each letter in pattern maps to exactly one 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.

Example 1 · Example:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation: a maps to "dog", and b maps to "cat".

Example 2 · Example:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation: a mapped to "dog" initially, but at the end maps to "fish".

Example 3 · Example:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Explanation: a cannot map to both "dog" and "cat".

Constraints:

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lowercase English letters and spaces ' '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Verify strict bijective mappings between character keys and string values.
  • Split strings into word tokens cleanly without extra whitespace errors.
  • Handle many-to-one collision detection.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Checking one-to-one and onto mapping between symbols and words.
  • Isomorphism between token sequences.

Algorithmic Decision Tree:

  • Bijective Map Verification
  • Token Synchronization

Connected Patterns:

Isomorphic StringsGroup AnagramsValid Anagram

1. Split and Word Set Validation

Intuition

Split s by space. If word count != pattern.length, return false. Map c to word. If c already seen, verify charToWord[c] == word. Else, verify word is not already in usedWords set; add to map and set.

When to apply: Basic baseline comparison.

Algorithm

  1. Split s into words.
  2. If pattern.length != words.length: return false.
  3. Initialize charToWord = {}, usedWords = Set().
  4. For i from 0 to pattern.length - 1:
  5. c = pattern[i], w = words[i].
  6. If c in charToWord:
  7. If charToWord[c] != w: return false.
  8. Else:
  9. If usedWords.has(w): return false.
  10. charToWord[c] = w; usedWords.add(w).
  11. Return true.

Split and Word Set Validation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [dog, cat, cat, dog]
Current operationSTEP 1 OF 6
Observation: Split s by spaces into array ["dog", "cat", "cat", "dog"]
Visual state
Values and pointers at this exact step
array
S
dog
cat
cat
dog
0
1
2
3
Variables at this step
Pattern Len
4
Words Len
4
Lengths Match
true
Check / comparison
Check lengths: pattern.length (4) == words.length (4).
Decision / next transition
Lengths match. Proceed to check bi-directional word mappings.
Why this step matters

Observation: Split s by spaces into array ["dog", "cat", "cat", "dog"].

Decision: pattern.length === words.length === 4. Continue validation.

Invariant: Equal token count.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5#include <unordered_map>
6#include <unordered_set>
7
8class Solution {
9public:
10 bool wordPattern(std::string pattern, std::string s) {
11 std::vector<std::string> words;
12 std::stringstream ss(s);
13 std::string word;
14 while (ss >> word) words.push_back(word);
15
16 if (pattern.size() != words.size()) return false;
17
18 std::unordered_map<char, std::string> c2w;
19 std::unordered_set<std::string> usedWords;
20
21 for (size_t i = 0; i < pattern.size(); ++i) {
22 char c = pattern[i];
23 const std::string& w = words[i];
24
25 if (c2w.count(c)) {
26 if (c2w[c] != w) return false;
27 } else {
28 if (usedWords.count(w)) return false;
29 c2w[c] = w;
30 usedWords.insert(w);
31 }
32 }
33 return true;
34 }
35};
36
37int main() {
38 Solution sol;
39 std::cout << (sol.wordPattern("abba", "dog cat cat dog") ? "true" : "false") << std::endl; // true
40 std::cout << (sol.wordPattern("abba", "dog cat cat fish") ? "true" : "false") << std::endl; // false
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N + M) — Splits string and processes N tokens in linear time.
  • Space complexity: O(N + M)

Why Brute Force Doesn't Scale:

Single pass index recording eliminates double map lookups.

Lightweight integer index maps.

2. Two Hash Maps Dual Mapping

Intuition

Maintain two maps c2w (char -> string) and w2c (string -> char). For each pair (c, w): verify c2w[c] == w and w2c[w] == c. Insert if absent.

When to apply: Standard symmetric formulation.

Algorithm

  1. Split s into words.
  2. If pattern.length != words.length: return false.
  3. Initialize c2w = {}, w2c = {}.
  4. For i from 0 to pattern.length - 1:
  5. c = pattern[i], w = words[i].
  6. If (c2w[c] && c2w[c] != w) || (w2c[w] && w2c[w] != c): return false.
  7. c2w[c] = w; w2c[w] = c.
  8. Return true.

Two Hash Maps Dual Mapping Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [dog, cat, cat, dog]
Current operationSTEP 1 OF 6
Observation: Use two maps: charToWord and wordToChar
Visual state
Values and pointers at this exact step
array
S
a<->dog
0
↑ i=0
Variables at this step
p2w
{"a":"dog"}
w2p
{"dog":"a"}
Check / comparison
Index 0: p2w['a']="dog", w2p["dog"]='a'. Both unmapped.
Decision / next transition
Establish dual mapping between 'a' and "dog".
Why this step matters

Observation: Use two maps: charToWord and wordToChar.

Decision: At index 0, register forward 'a' -> "dog" and reverse "dog" -> 'a'.

Invariant: 1-to-1 mapping initialized.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5#include <unordered_map>
6
7class Solution {
8public:
9 bool wordPattern(std::string pattern, std::string s) {
10 std::vector<std::string> words;
11 std::stringstream ss(s);
12 std::string word;
13 while (ss >> word) words.push_back(word);
14
15 if (pattern.size() != words.size()) return false;
16
17 std::unordered_map<char, std::string> c2w;
18 std::unordered_map<std::string, char> w2c;
19
20 for (size_t i = 0; i < pattern.size(); ++i) {
21 char c = pattern[i];
22 const std::string& w = words[i];
23
24 if (c2w.count(c) && c2w[c] != w) return false;
25 if (w2c.count(w) && w2c[w] != c) return false;
26
27 c2w[c] = w;
28 w2c[w] = c;
29 }
30 return true;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::cout << (sol.wordPattern("abba", "dog cat cat dog") ? "true" : "false") << std::endl; // true
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N + M) — Linear time token processing with two hash tables.
  • Space complexity: O(N + M)

3. Index Mapping / First-Seen Synchronization (Optimal)

Intuition

Split s into words. If pattern.length != words.length, return false. Maintain a map storing the last seen position of each character and word. If the last seen index of pattern[i] differs from the last seen index of words[i], a bijection violation has occurred. Update both to i + 1.

When to apply: The standard gold standard solution matching Isomorphic Strings.

Algorithm

  1. Split s into words.
  2. If pattern.length != words.length: return false.
  3. Initialize charIndex = {}, wordIndex = {}.
  4. For i from 0 to pattern.length - 1:
  5. c = pattern[i], w = words[i].
  6. If charIndex[c] != wordIndex[w]: return false.
  7. charIndex[c] = i + 1; wordIndex[w] = i + 1.
  8. Return true.

Bijection Consistency Mapping Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, b, a]
Current operationSTEP 1 OF 6
Observation: Split s by space into 4 words: ["dog", "cat", "cat", "dog"]
Visual state
Values and pointers at this exact step
array
S
a
b
b
a
0
↑ i=0: 'a' <-> "dog"
1
2
3
Variables at this step
Index
0
Pattern Char
a
Word
dog
pToW
{ a: 'dog' }
wToP
{ dog: 'a' }
Check / comparison
Neither 'a' nor "dog" mapped. Establish map: 'a' <-> "dog".
Decision / next transition
Valid bijection initialized for index 0.
Why this step matters

Observation: Split s by space into 4 words: ["dog", "cat", "cat", "dog"]. Pattern length (4) matches word count (4).

Decision: At i = 0, neither 'a' nor "dog" has been mapped. Establish bidirectional link: 'a' -> "dog" and "dog" -> 'a'.

Invariant: One-to-one bijection holds for index 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5#include <unordered_map>
6
7class Solution {
8public:
9 bool wordPattern(std::string pattern, std::string s) {
10 std::vector<std::string> words;
11 std::stringstream ss(s);
12 std::string word;
13 while (ss >> word) words.push_back(word);
14
15 if (pattern.size() != words.size()) return false;
16
17 std::unordered_map<char, int> charIndex;
18 std::unordered_map<std::string, int> wordIndex;
19
20 for (int i = 0; i < (int)pattern.size(); ++i) {
21 char c = pattern[i];
22 const std::string& w = words[i];
23
24 if (charIndex[c] != wordIndex[w]) return false;
25
26 charIndex[c] = i + 1;
27 wordIndex[w] = i + 1;
28 }
29 return true;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << (sol.wordPattern("abba", "dog cat cat dog") ? "true" : "false") << std::endl; // true
36 std::cout << (sol.wordPattern("abba", "dog cat cat fish") ? "true" : "false") << std::endl; // false
37 std::cout << (sol.wordPattern("aaaa", "dog cat cat dog") ? "true" : "false") << std::endl; // false
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N + M) strictly — Single linear pass over pattern and word tokens.
  • Space complexity: O(N + M)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Two Hash Maps BijectionO(N + M)O(N + M)Extremely intuitive, explicit forward and reverse mapping checks.Requires two hash maps.
2.Single Map with Word SetO(N + M)O(N + M)One map + one set.Slightly less symmetric.
3.First Seen Index Normalization (Optimal)OptimalO(N + M)O(N + M)Directly compares last-seen / first-seen index timestamps.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Checking only char->word mapping, allowing two distinct characters to map to the same word.

Pitfall 2:

Using Java Integer object comparison with == instead of .equals() or Objects.equals().

Crucial Edge Cases to Validate:

  • Word count differs from pattern length (pattern = aaa, s = 'aa aa aa aa'): Length mismatch check returns false in O(1).
  • Multiple characters map to same word (pattern = abba, s = 'dog dog dog dog'): i=1: charIndex[b] is undefined while wordIndex[dog] is 1 -> mismatch caught.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the bijection concept and how it directly relates to LeetCode 205 (Isomorphic Strings).
  2. Point out the Integer object reference equality pitfall in Java.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must both directions of mapping (char->word and word->char) be verified?

Back to DSA Sheet