#290
Word Pattern
Easy Two-way HashMap
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a sentence follows a pattern of letters, where each letter maps to exactly one word and each word to exactly one letter.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does each letter stand for exactly one word, and each word for one letter?
Why this works: two maps, one per direction; any conflict fails.
Example: "abba" and "dog cat cat dog"
a→dog, b→cat, b→cat ✓, a→dog ✓ → true✦Hints open one at a time
Split the sentence; the word count must equal the pattern length.
Keep char → word and word → char maps, and check both.
↗Approach
For each position, if either map has a conflicting entry, return false; otherwise store both directions.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (words.length != pattern.length()) return false;
Map<Character, String> cw = new HashMap<>();
Map<String, Character> wc = new HashMap<>();
for (int i = 0; i < words.length; i++) {
char c = pattern.charAt(i);
String w = words[i];
if (cw.containsKey(c) && !cw.get(c).equals(w)) return false;
if (wc.containsKey(w) && wc.get(w) != c) return false;
cw.put(c, w);
wc.put(w, c);
}
return true;
}
}!Common mistake
Checking only char → word, so "abba" with "dog dog dog dog" passes wrongly.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon