A routing table treated a short pattern as a contract: each letter named a token slot, and the same letter always meant the same word. The first version, for each new slot, rescanned every earlier pairing to see if the contract still held. A handful of rules in staging returned instantly. Tens of thousands of production routes were still proving consistency when the request timed out.

Word Pattern asks whether a bijection exists between pattern chars and words. pattern.charAt(i) is already free. Nested consistency uses that and still pays O(n²). Two maps — letter to word, word to letter — refuse a letter that changes partners and a word claimed by two letters.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about recording both directions so two letters cannot share one token.

The problem

Given a pattern string of characters and a string s of space-separated words, return true if they follow the same pattern and false otherwise. The same letter always maps to the same word. No two letters map to the same word. Pattern length must equal the number of tokens.

pattern = "xyyx",  s = "oak pine pine oak"   →  true
pattern = "xyyx",  s = "oak pine pine elm"   →  false
pattern = "xxxx",  s = "oak pine pine oak"   →  false
pattern = "ab",    s = "dog dog"             →  false   two letters, one word
pattern = "abc",   s = "oak pine"            →  false   token count ≠ pattern length

Note: Compare pattern length to the token count after the split, not to s.length(). s.length() counts spaces too.

Nested consistency is the honest brute force

Split s on single spaces. If the token count disagrees with the pattern, return false. Otherwise, for each index i, rescan every earlier j. If the letters match but the words do not, the forward pairing broke. If the letters differ but the words match, two letters collapsed onto one token. Correct. Quadratic.

boolean wordPatternNested(String pattern, String s) {
    String[] words = s.split(" ");
    if (words.length != pattern.length()) {
        return false;
    }
    for (int i = 0; i < pattern.length(); i++) {
        for (int j = 0; j < i; j++) {
            boolean sameLetter = pattern.charAt(i) == pattern.charAt(j);
            boolean sameWord = words[i].equals(words[j]);
            if (sameLetter != sameWord) {
                return false;
            }
        }
    }
    return true;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested rescan for a question two maps answer in one pass: does this letter already have a different word — or this word a different letter?

Split, then pair both ways

Split s. If the token count is not the pattern length, return false. Then two HashMaps: letter → word and word → letter.

  • Let c = pattern.charAt(i) and w = words[i].
  • If c is already mapped and the partner is not w, false.
  • If w is already mapped and the partner is not c, false.
  • Record both and continue.

You never restart a scan from index 0. You never trust one direction. A map plus a set of used words is the same bijection: refuse a new letter whose word is already claimed.

pattern = "xyyx"   s = "oak pine pine oak"

split → [oak, pine, pine, oak]  length 4 == 4

i=0  x→oak, oak→x
i=1  y→pine, pine→y
i=2  y already → pine, words[2]=pine  match
i=3  x already → oak, words[3]=oak  match
true

pattern = "ab"   s = "dog dog"

split → [dog, dog]  length 2 == 2

i=0  a→dog, dog→a
i=1  b unmapped; dog already → a, partner ≠ b  false

The Java is that walk:

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

Time is expected O(n) — one pass over the tokens, a constant number of lookups and puts per index. Space is O(n) for the split array and the maps. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: One forward map is not a bijection. pattern = "ab" and s = "dog dog" stores a → dog, then b → dog. The letter map never complains. The inverse does: dog cannot partner both a and b. Split on a single space. Java split(" ") drops trailing empties; a leading or doubled space becomes an empty token. "".split(" ") is one empty string, not zero tokens.

What interviewers usually poke next

  • Isomorphic strings. Same bijection, two character strings instead of a pattern and a token list. The trap is still one map.
  • Unicode. Pattern letters and words are already map keys. There is no 26-slot shortcut the way Valid Anagram has for a–z.
  • No split. Walk s as a char[], emit a token at each single space, and pair it with pattern.charAt(i) as you go. Leftover characters or leftover pattern letters are a false. Same two maps.
  • Used-word set instead of the inverse map. Contains Duplicate is the same “have I seen this key?” test. Insert the word when you first bind a letter; a new letter whose word is already in the set is a reverse collision. Two Sum is the same one-pass map habit on a different question; Ransom Note and First Unique Character count letters instead of pairing them.

You are done with this problem when you can say, out loud, why the nested consistency scan is correct, why one map accepts "ab" / "dog dog", and why the reverse map (or the used-word set) is the bijection, not decoration.