Introduction

The "word pattern" problem asks whether a string of space-separated words maps one-to-one with a pattern string of characters. For example, pattern "abba" and string "dog cat cat dog" match because a→dog and b→cat are consistent in both directions. This is a classic hash-map problem (LeetCode 290) that tests bijection — every pattern character maps to exactly one word, and every word maps to exactly one pattern character. The solution runs in O(n) time using two dictionaries.

Hash Map Approach (Python)

1def word_pattern(pattern: str, s: str) -> bool:
2    words = s.split()
3    if len(pattern) != len(words):
4        return False
5
6    char_to_word = {}
7    word_to_char = {}
8
9    for ch, word in zip(pattern, words):
10        if ch in char_to_word:
11            if char_to_word[ch] != word:
12                return False
13        else:
14            char_to_word[ch] = word
15
16        if word in word_to_char:
17            if word_to_char[word] != ch:
18                return False
19        else:
20            word_to_char[word] = ch
21
22    return True
23
24# Examples
25print(word_pattern("abba", "dog cat cat dog"))   # True
26print(word_pattern("abba", "dog cat cat fish"))  # False
27print(word_pattern("aaaa", "dog cat cat dog"))   # False
28print(word_pattern("abba", "dog dog dog dog"))   # False

Two dictionaries enforce the bijection: char_to_word maps pattern characters to words, and word_to_char maps words back to pattern characters. If either direction conflicts, the pattern does not match.

Java Implementation

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

Index-Based Approach

An alternative uses the index of first occurrence for both the character and the word at each position:

1def word_pattern_index(pattern: str, s: str) -> bool:
2    words = s.split()
3    if len(pattern) != len(words):
4        return False
5
6    # Map each character/word to the index of its first occurrence
7    return [pattern.index(c) for c in pattern] == \
8           [words.index(w) for w in words]
9
10print(word_pattern_index("abba", "dog cat cat dog"))  # True
11print(word_pattern_index("abba", "dog cat cat fish")) # False

This is concise but runs in O(n²) because index() scans the list each time. The hash-map approach is O(n).

Isomorphic Strings Variant

A closely related problem is checking if two strings are isomorphic (LeetCode 205), where each character in string s maps to exactly one character in string t:

1def is_isomorphic(s: str, t: str) -> bool:
2    if len(s) != len(t):
3        return False
4
5    s_to_t = {}
6    t_to_s = {}
7
8    for cs, ct in zip(s, t):
9        if cs in s_to_t and s_to_t[cs] != ct:
10            return False
11        if ct in t_to_s and t_to_s[ct] != cs:
12            return False
13        s_to_t[cs] = ct
14        t_to_s[ct] = cs
15
16    return True
17
18print(is_isomorphic("egg", "add"))    # True
19print(is_isomorphic("foo", "bar"))    # False
20print(is_isomorphic("paper", "title")) # True

The logic is identical — the only difference is that word pattern splits a string into words while isomorphic strings compares character by character.

Regex Pattern Matching Variant

For actual regex-style pattern matching where the pattern contains wildcards, use the re module:

1import re
2
3# Check if string matches a regex pattern
4print(bool(re.fullmatch(r"ab+a", "abba")))   # True
5print(bool(re.fullmatch(r"ab+a", "aba")))     # True
6print(bool(re.fullmatch(r"ab+a", "aca")))     # False

This is a different problem — regex matching checks character-level patterns, not word-level bijections.

Common Pitfalls

• Only checking one direction of the mapping: Mapping char→word alone is not enough. Pattern "abba" with string "dog dog dog dog" would incorrectly return true because a→dog and b→dog are both valid forward mappings. The reverse map word→char catches this by detecting that dog maps to both a and b.
• Forgetting to check length equality: If the pattern has 4 characters but the string has 3 words, the answer is always false. Skipping this check can cause index errors or incorrect matches on partial data.
• Using split() vs split(" ") incorrectly: In Python, "a b".split() produces ["a", "b"] (splits on any whitespace, removes empties), while "a b".split(" ") produces ["a", "", "b"] (splits on single space, keeps empties). Use split() for the word pattern problem to handle multiple spaces.
• Confusing this problem with regex matching: The word pattern problem checks bijection between pattern characters and words. It has nothing to do with regex wildcards like *, +, or .. These are fundamentally different problems.
• Not handling empty inputs: An empty pattern with an empty string should return true. An empty pattern with a non-empty string (or vice versa) should return false. The length check handles this, but edge cases are easy to miss in interviews.

Summary

• Use two hash maps to enforce a one-to-one (bijective) mapping between pattern characters and words
• Check both directions: char→word and word→char — one direction alone allows false positives
• Always verify that the pattern length equals the word count before comparing
• Time complexity is O(n) with hash maps, O(n²) with the index-based approach
• The same bijection technique solves isomorphic strings (LeetCode 205) and similar mapping problems