Approach

Word Pattern

Approach

Use bidirectional hash maps to verify pattern-word bijection.

Algorithm

Split string into words
Check if pattern length matches word count
Create two maps: char→word and word→char
For each (char, word) pair:
- Verify existing mappings are consistent
- Add new mappings if not exist
Return true if all checks pass

Complexity

Time: O(n + m) where n is pattern length, m is string length
Space: O(w) where w is number of unique words

Key Insights

Similar to Isomorphic Strings but with words instead of characters
Need bidirectional mapping for full bijection
Pattern "abba" with "dog dog dog dog" should fail

Solution

java

1class Solution {
2    public boolean wordPattern(String pattern, String s) {
3        String[] words = s.split(" ");
4        
5        if (pattern.length() != words.length) return false;
6        
7        Map<Character, String> charToWord = new HashMap<>();
8        Map<String, Character> wordToChar = new HashMap<>();
9        
10        for (int i = 0; i < pattern.length(); i++) {
11            char c = pattern.charAt(i);
12            String word = words[i];
13            
14            if (charToWord.containsKey(c)) {
15                if (!charToWord.get(c).equals(word)) return false;
16            } else {
17                charToWord.put(c, word);
18            }
19            
20            if (wordToChar.containsKey(word)) {
21                if (wordToChar.get(word) != c) return false;
22            } else {
23                wordToChar.put(word, c);
24            }
25        }
26        
27        return true;
28    }
29}