Logo

Kode$word

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words
LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

Learn How to Solve the Word Pattern Problem Using HashMaps, Bidirectional Mapping, and Index Mapping Techniques

10 views
0
0
HashMapString ManipulationBijection MappingTwo HashMapsIndex MappingLeetCode Easy
Github icon

Try the Problem

You can practice the problem here:

https://leetcode.com/problems/word-pattern/


Problem Description

You are given:

  1. A string pattern
  2. A string s

The string s consists of words separated by spaces.

Your task is to determine whether s follows the same pattern defined by the string pattern.

To follow the pattern, there must be a bijection between pattern characters and words.


Understanding the Meaning of Bijection

A bijection means a one-to-one relationship between two sets.

For this problem it means:

  1. Every character in the pattern maps to exactly one word.
  2. Every word maps to exactly one pattern character.
  3. Two characters cannot map to the same word.
  4. Two words cannot map to the same character.

This ensures the mapping is unique in both directions.


Example Walkthrough

Example 1

Input

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

Output

true

Explanation

Mapping:

a → dog
b → cat

Pattern:

a b b a

Words:

dog cat cat dog

The mapping is perfectly consistent.

Example 2

Input

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

Output

false

Explanation

The last word "fish" breaks the pattern because "a" was already mapped to "dog".

Example 3

Input

pattern = "aaaa"
s = "dog cat cat dog"

Output

false

Explanation

Pattern requires:

a → same word every time

But the words differ.


Constraints

1 <= pattern.length <= 300
pattern contains lowercase English letters

1 <= s.length <= 3000
s contains lowercase letters and spaces
words are separated by a single space
no leading or trailing spaces


Core Observation

Before applying any algorithm, we should verify one simple condition.

If the number of pattern characters does not match the number of words, then the pattern cannot match.

Example:

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

Pattern length = 4

Words = 3

This automatically returns false.


Thinking About Possible Approaches

While solving this problem, several strategies may come to mind:

  1. Use one HashMap to store pattern → word mapping and check duplicates manually.
  2. Use two HashMaps to enforce bijection from both directions.
  3. Track first occurrence indices of pattern characters and words.
  4. Compare mapping patterns using arrays or maps.

Let’s explore these approaches one by one.


Approach 1: Single HashMap (Your Solution)

Idea

We store mapping:

pattern character → word

While iterating:

  1. If the character already exists in the map
  2. → check if it maps to the same word.
  3. If it does not exist
  4. → ensure that no other character already maps to that word.

This ensures bijection.

Java Implementation

class Solution {

public boolean wordPattern(String pattern, String s) {

String words[] = s.split(" ");

// Length mismatch means impossible mapping
if(pattern.length() != words.length) return false;

HashMap<Character,String> mp = new HashMap<>();

for(int i = 0; i < words.length; i++){

char ch = pattern.charAt(i);

if(mp.containsKey(ch)){

if(!mp.get(ch).equals(words[i])){
return false;
}

}else{

// Prevent two characters mapping to same word
if(mp.containsValue(words[i])){
return false;
}
}

mp.put(ch, words[i]);
}

return true;
}
}

Time Complexity

O(n²)

Because containsValue() can take O(n) time in worst case.

Space Complexity

O(n)


Approach 2: Two HashMaps (Cleaner Bijection Enforcement)

Idea

Instead of checking containsValue, we maintain two maps.

pattern → word
word → pattern

This ensures bijection naturally.

Java Implementation

class Solution {

public boolean wordPattern(String pattern, String s) {

String[] words = s.split(" ");

if(pattern.length() != words.length)
return false;

HashMap<Character, String> map1 = new HashMap<>();
HashMap<String, Character> map2 = new HashMap<>();

for(int i = 0; i < pattern.length(); i++){

char ch = pattern.charAt(i);
String word = words[i];

if(map1.containsKey(ch) && !map1.get(ch).equals(word))
return false;

if(map2.containsKey(word) && map2.get(word) != ch)
return false;

map1.put(ch, word);
map2.put(word, ch);
}

return true;
}
}

Time Complexity

O(n)

Because both maps allow constant-time lookups.

Space Complexity

O(n)


Approach 3: Index Mapping Technique (Elegant Trick)

Idea

Another clever technique is to compare first occurrence indices.

Example:

pattern = abba
words = dog cat cat dog

Pattern index sequence:

a → 0
b → 1
b → 1
a → 0

Words index sequence:

dog → 0
cat → 1
cat → 1
dog → 0

If the index sequences match, then the pattern holds.

Java Implementation

class Solution {

public boolean wordPattern(String pattern, String s) {

String[] words = s.split(" ");

if(pattern.length() != words.length)
return false;

HashMap<Character,Integer> map1 = new HashMap<>();
HashMap<String,Integer> map2 = new HashMap<>();

for(int i = 0; i < pattern.length(); i++){

char ch = pattern.charAt(i);
String word = words[i];

if(!map1.getOrDefault(ch, -1)
.equals(map2.getOrDefault(word, -1))){
return false;
}

map1.put(ch, i);
map2.put(word, i);
}

return true;
}
}

Time Complexity

O(n)

Space Complexity

O(n)


Comparison of Approaches

ApproachTime ComplexitySpace ComplexityNotes
Single HashMapO(n²)O(n)Simple but slower
Two HashMapsO(n)O(n)Cleaner bijection enforcement
Index MappingO(n)O(n)Elegant and interview-friendly


Key Interview Insight

Problems like this test your understanding of:

Bijection Mapping

Similar problems include:

  1. Isomorphic Strings
  2. Word Pattern II
  3. Substitution Cipher Problems

Understanding how to enforce one-to-one mappings is a powerful technique.


Conclusion

The Word Pattern problem is an excellent example of how HashMaps can enforce relationships between two datasets.

While a simple HashMap solution works, more optimized methods like two-way mapping or index comparison provide cleaner and more efficient implementations.

Mastering these techniques will help you solve many pattern-matching and mapping problems commonly asked in coding interviews.

Related Articles

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Learn how to determine whether a binary string contains only one continuous group of 1s. This article explains the problem clearly, builds the intuition step-by-step, and walks through a clean Java solution with time complexity analysis.

Read Article
LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

A Complete Guide to Solving “Find Unique Binary String” Using Hashing, Brute Force Thinking, and Cantor’s Diagonalization

Read Article
Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Understand how to convert a binary string into an alternating pattern with the minimum number of flips using a simple greedy approach.

Read Article
Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Using Frequency Counting to Construct the Largest Possible Palindrome

Read Article

Ai Assistant Kas