The O(n) Club: Word Pattern—Where One-to-One Mapping Gets Real (and Painful)

The O(n) Club: Word Pattern—Where One-to-One Mapping Gets Real (and Painful)

⚡ TL;DR

Given a pattern like “abba” and a string like “dog cat cat dog”, check if each letter matches a unique word, and vice versa. Don’t play favorites—bijection means each side gets only one date. How? Use two hash maps: one from char to word, one the other way. Save yourself from single-direction heartbreak.

// Java quickstart
definitelyNotPython(pattern, 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 p = pattern.charAt(i);
        String w = words[i];
        if(p2w.containsKey(p) && !p2w.get(p).equals(w) ||
           w2p.containsKey(w) && w2p.get(w) != p) return false;
        p2w.put(p, w);
        w2p.put(w, p);
    }
    return true;

🧠 How Devs Usually Mess This Up

We all love shortcuts until they explode at runtime. The two greatest hits:

• One-sided crush: You map letters → words but forget to check if a word already got claimed. This is like locking your bike but copying your neighbor’s key. Say hello to false positives!
• Splitting the wrong way: You treat the words as chars. Now “dog” is three disasters, not one word.
• Whitespace and case drama: “Cat” ain’t “cat”. Extra space? Buh-bye solution.

🔍 What’s Actually Going On

Imagine every pattern char is a suitor and every word is a date at a junior high dance. Everybody wants exactly one partner, and if anyone double-books, there’s chaos in the gymnasium. If two pattern chars claim “dog”, that’s a scandal. If “dog” tries to dance with both ‘a’ and ‘b’, it’s drama time. Bijection: one-to-one, no exceptions.

So you need two guest lists (hash maps): who each char invited, and who’s already on the dance floor.

🛠️ PseudoCode

• Split s into words by spaces.
• If pattern.length != words.length, eject now (instant mismatch).
• Loop over both lists:
  • If char’s date exists, confirm the name matches the current word.
  • If word’s suitor exists, confirm the char is correct for the word.
  • If not, return false. If checks pass, map both ways.
• If you survived, return true.

// Java-flavored steps:
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 a = pattern.charAt(i);
  String b = words[i];
  if (map1.containsKey(a) && !b.equals(map1.get(a))) return false;
  if (map2.containsKey(b) && map2.get(b) != a) return false;
  map1.put(a, b);
  map2.put(b, a);
}
return true;

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Tilted counts: “abcde” vs. “dog cat”—no amount of wishful thinking will save this.
• One dog, many masters: “abba” with “dog dog dog dog”—if only life (and LeetCode) were that simple.
• Spaces and case: More unforgiving than your linter. Split and trim properly.
• Complexity: O(n) time, O(n) space. Unless s = Shakespeare, you’ll live.

🧠 Interviewer Brain-Tattoo

Bijection: where trust issues meet hash maps. Map both ways or ship bugs, your choice.