Problem statement

Given a pattern and a string s, determine whether s follows the same pattern: there is a bijection between letters in pattern and non-empty words in s (words are separated by single spaces).

Example 1

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Constraints

• 1 <= pattern.length <= 10
• s contains lowercase words separated by single spaces.

Hints for Word Pattern

1. Hint 1

   This is Isomorphic Strings where one side is words instead of characters.

2. Hint 2

   Lengths must match first: number of words == pattern length.

How to solve Word Pattern

This is Isomorphic Strings with words on one side instead of characters. Split s on spaces and require a bijection between pattern letters and words — checked in both directions, so neither two letters share a word nor one letter takes two words.

Approach

1. Split s into words; if the count differs from the pattern's length, return false immediately.
2. Track, for each pattern letter and for each word, the index at which it first appeared.
3. At each position, compare the letter's first index with the word's first index.
4. If they disagree, the pairing is inconsistent — return false.
5. Otherwise record both first indices on their debut and continue.

Why it works

Comparing first-occurrence indices captures both halves of the bijection in a single test: if a letter has been seen before but its word has not (or vice versa), the indices differ and the check fails, catching both a letter mapping to two words and two letters mapping to one word. Two separate lookup tables would express the same thing; this formulation just makes the symmetry explicit.

Complexity

• Time — O(|s|)
• Space — O(number of distinct words)

Pitfalls

• Check the counts first — "abba" against three words can never match, and skipping the guard leads to out-of-range reads.
• One direction is not enough: "aaaa" against "dog cat cat dog" must fail, and only the reverse check catches it.
• Words are separated by single spaces; splitting naively on whitespace runs is a different parse.
• A letter mapping to the identical word each time is fine, not a special case.

Reference solution

Python

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(words) != len(pattern):
        return False
    m1 = {}
    m2 = {}
    for a, b in zip(pattern, words):
        if a in m1 and m1[a] != b:
            return False
        if b in m2 and m2[b] != a:
            return False
        m1[a] = b
        m2[b] = a
    return True

Java

public static boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (words.length != pattern.length()) return false;
    int[] charFirst = new int[128];
    Arrays.fill(charFirst, -1);
    Map<String, Integer> wordFirst = new HashMap<>();
    for (int i = 0; i < pattern.length(); i++) {
        int c = pattern.charAt(i);
        String w = words[i];
        int ci = charFirst[c];
        int wi = wordFirst.containsKey(w) ? wordFirst.get(w) : -1;
        if (ci != wi) return false;
        if (ci == -1) {
            charFirst[c] = i;
            wordFirst.put(w, i);
        }
    }
    return true;
}

C++

bool wordPattern(string pattern, string s) {
    vector<string> words;
    string cur;
    for (char ch : s) {
        if (ch == ' ') {
            words.push_back(cur);
            cur.clear();
        } else {
            cur += ch;
        }
    }
    words.push_back(cur);
    if (words.size() != pattern.size()) return false;
    vector<int> charFirst(128, -1);
    map<string, int> wordFirst;
    for (int i = 0; i < (int) pattern.size(); i++) {
        int c = (unsigned char) pattern[i];
        string w = words[i];
        int ci = charFirst[c];
        int wi = wordFirst.count(w) ? wordFirst[w] : -1;
        if (ci != wi) return false;
        if (ci == -1) {
            charFirst[c] = i;
            wordFirst[w] = i;
        }
    }
    return true;
}

JavaScript

var wordPattern = function(pattern, s) {
    const words = s.split(" ").filter(function(w) { return w !== ""; });
    if (words.length !== pattern.length) return false;
    const m1 = new Map(), m2 = new Map();
    for (let i = 0; i < pattern.length; i++) {
        const a = pattern[i], b = words[i];
        if (m1.has(a) && m1.get(a) !== b) return false;
        if (m2.has(b) && m2.get(b) !== a) return false;
        m1.set(a, b);
        m2.set(b, a);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy