#290 Word Pattern
the problem
In plain words
pattern is a string of letters and s is a sentence of words separated by single spaces. Return true if s follows pattern: letters and words pair up one-to-one, so each letter always stands for the same word and no two letters stand for the same word.
in pattern = "abba", s = "dog cat cat dog"
out true
in pattern = "abba", s = "dog cat cat fish"
out false
in pattern = "aaaa", s = "dog cat cat dog"
out false
- 1 ≤ pattern.length ≤ 300, lowercase letters
- 1 ≤ s.length ≤ 3000, lowercase words separated by single spaces (no leading or trailing spaces)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)Group by a canonical key
It's Isomorphic Strings with words instead of characters: one map letter → word, one map word → letter — and the same number of letters and words.
solutions
From brute force to optimal
Positions i and j must have equal letters exactly when they have equal words.
- Split s; different counts → false.
- For every i and j < i: (pattern[i] == pattern[j]) must equal words[i].equals(words[j]).
n(n − 1)/2 pairs of positions, each comparing words of length up to L.
The array of words from split.
class Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (words.length != pattern.length()) return false; for (int i = 0; i < words.length; i++) { for (int j = 0; j < i; j++) { boolean sameLetter = pattern.charAt(i) == pattern.charAt(j); boolean sameWord = words[i].equals(words[j]); // equals, never == on Strings if (sameLetter != sameWord) return false; } } return true; }}letterToWord and wordToLetter; putIfAbsent returns the existing value, so a conflict shows up at once.
- Split s; different counts → false.
- knownWord = letterToWord.putIfAbsent(c, w); knownLetter = wordToLetter.putIfAbsent(w, c).
- Either exists and differs → false.
Hashing a word costs its length; everything else is O(1) per position.
The words and the two maps.
class Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (words.length != pattern.length()) return false; // one word per letter Map<Character, String> letterToWord = new HashMap<>(); Map<String, Character> wordToLetter = new HashMap<>(); for (int i = 0; i < words.length; i++) { char c = pattern.charAt(i); String w = words[i]; String knownWord = letterToWord.putIfAbsent(c, w); // null if c is new Character knownLetter = wordToLetter.putIfAbsent(w, c); if (knownWord != null && !knownWord.equals(w)) return false; if (knownLetter != null && knownLetter != c) return false; } return true; }}Put the letter and the word into one Map<Object, Integer>; they must have been last seen at the same index.
- a = map.put(letter, i); b = map.put(word, i).
- If !Objects.equals(a, b) → false.
Same hashing cost as two maps.
One map holding letters and words.
class Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if (words.length != pattern.length()) return false; Map<Object, Integer> lastSeen = new HashMap<>(); // a Character and a String never collide as keys for (int i = 0; i < words.length; i++) { Integer a = lastSeen.put(pattern.charAt(i), i); // where this letter appeared last Integer b = lastSeen.put(words[i], i); // where this word appeared last if (!Objects.equals(a, b)) return false; // NOT a != b: that compares Integer objects } return true; }}in the room
How to say it in the interview
talk track
- Split with
s.split(" ")and compare the counts first. - Explain both directions with "abba" / "dog dog dog dog": a → dog and b → dog must fail.
- If you use the index trick, call out
Objects.equals—!=on twoIntegers breaks past 127.
traps
- Mapping only letter → word: "abba" vs "dog dog dog dog" passes wrongly.
map.put(c, i) != map.put(w, i)compares two Integer objects: right up to index 127 (the Integer cache), wrong after.- Comparing words with
==instead ofequals.
what they ask next
Follow-ups
Word Pattern II (LC 291, Premium): no spaces, so you choose where each word ends?
Backtracking: for the next letter, try every possible next word, keeping both maps consistent, and undo on the way back.
before you submit
Edge cases to test
- Different counts ("aaa" vs "dog dog") → false.
- Two letters, one word ("ab" vs "dog dog") → false.
- More than 127 words: index-based tricks must compare with
equals, not!=.
practise next
Similar problems
- #205Isomorphic StringsEasyin Hashing
- #49Group AnagramsMediumin Arrays & Strings