206. Word Pattern

Split s into words and pair each pattern letter with a word. Maintain a letter-to-word map and a word-to-letter map; any disagreement in either direction means the pattern isn't followed.

Idea

A valid match is a bijection between pattern letters and words. Just like Isomorphic Strings, one map isn't enough — we need letter→word and word→letter to reject two letters mapping to the same word (or vice-versa).

Algorithm

1. Split s into words. If len(pattern) != len(words), return false.
2. For each (letter, word) pair:
   • If letter is mapped and p2w[letter] != word, return false.
   • If word is mapped and w2p[word] != letter, return false.
   • Record both directions.
3. Return true.

Worked example: pattern = "abba", s = "dog cat cat dog"

• a↔dog, b↔cat, b↔cat (consistent), a↔dog (consistent) → true.

Contrast "abba", "dog cat cat fish": last pair a↔fish conflicts with a↔dog → false.

Complexity

• Time: O(n) over pattern length / words.
• Space: O(n) for the two maps.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }
        Map<Character, String> p2w = new HashMap<>();
        Map<String, Character> w2p = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String w = words[i];
            if (p2w.containsKey(c) && !p2w.get(c).equals(w)) {
                return false;
            }
            if (w2p.containsKey(w) && w2p.get(w) != c) {
                return false;
            }
            p2w.put(c, w);
            w2p.put(w, c);
        }
        return true;
    }
}