Word Pattern

Published at24 Jul 2026

Like0

Given a pattern string like "abba" and a string s of space-separated words like "dog cat cat dog", determine if s follows the same pattern. That means there is a bijection between each character in the pattern and each word in s. A letter maps to exactly one word, and each word maps to exactly one letter.

This is a classic hash map problem requiring bidirectional mapping. A single hash map is not enough because it only enforces one direction. For example, pattern "abba" with "dog dog dog dog" would be incorrectly accepted with a one-way map (a→dog, b→dog) because both letters map to the same word. A second hash map tracking word→letter catches this violation.

The algorithm splits the words from s and compares the length of the pattern with the word count. Then it iterates through both, building the two maps simultaneously. If at any point a mapping contradicts an existing one, return false. This runs in O(n) time where n is the length of the pattern (or number of words).

Edge cases include empty pattern or empty string, a pattern longer than the word list, and patterns where multiple letters map to the same word.

Example Input & Output

Example 1

Input

"abba", "dog cat cat dog"

Output

true

Explanation

Bijection holds: a→dog, b→cat.

Example 2

Input

"aaaa", "dog cat cat dog"

Output

false

Explanation

Each a maps to different words.

Example 3

Input

"abba", "dog cat cat fish"

Output

false

Explanation

Last word breaks mapping.

Example 4

Input

"abba", "dog dog dog dog"

Output

false

Explanation

b maps to dog but a already maps to dog.

Example 5

Input

"", ""

Output

true

Explanation

Empty pattern and empty string match.

Algorithm Flow

Recommendation Algorithm Flow for Word Pattern

Solution Approach

Check if a string follows a given pattern, where each character in the pattern maps to a word in the string. Split the string into words. If the pattern length differs from the word count, return false. Build a bijection map from pattern characters to words and vice versa. If a mapping conflicts, return false.

function wordPattern(pattern, s) {
  var words = s.split(' '), pMap = {}, wMap = {};
  if (pattern.length !== words.length) return false;
  for (var i = 0; i < pattern.length; i++) {
    var p = pattern[i], w = words[i];
    if (pMap[p] && pMap[p] !== w) return false;
    if (wMap[w] && wMap[w] !== p) return false;
    pMap[p] = w; wMap[w] = p;
  }
  return true;
}

The bijection ensures the mapping is one-to-one in both directions. 'abba' and 'dog cat cat dog' is valid; 'abba' and 'dog cat cat fish' is not because 'a' would map to both 'dog' and 'fish'.

Time complexity is O(n), space complexity is O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public boolean solution(String pattern, String s) {
        if (pattern.isEmpty() && s.isEmpty()) return true;
        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 ch = pattern.charAt(i);
            String w = words[i];
            if (p2w.containsKey(ch) && !p2w.get(ch).equals(w)) return false;
            if (w2p.containsKey(w) && w2p.get(w) != ch) return false;
            p2w.put(ch, w);
            w2p.put(w, ch);
        }
        return true;
    }
}

javascript

function solution(pattern, s) {
  if (!pattern && !s) return true;
  var words = s.split(' ');
  if (pattern.length !== words.length) return false;
  var p2w = {}, w2p = {};
  for (var i = 0; i < pattern.length; i++) {
    var ch = pattern[i], w = words[i];
    if (p2w[ch] && p2w[ch] !== w) return false;
    if (w2p[w] && w2p[w] !== ch) return false;
    p2w[ch] = w;
    w2p[w] = ch;
  }
  return true;
}

php

<?php
function solution($pattern, $s) {
    if ($pattern === '' && $s === '') return true;
    $words = explode(' ', $s);
    if (strlen($pattern) !== count($words)) return false;
    $p2w = [];
    $w2p = [];
    for ($i = 0; $i < strlen($pattern); $i++) {
        $ch = $pattern[$i];
        $w = $words[$i];
        if (isset($p2w[$ch]) && $p2w[$ch] !== $w) return false;
        if (isset($w2p[$w]) && $w2p[$w] !== $ch) return false;
        $p2w[$ch] = $w;
        $w2p[$w] = $ch;
    }
    return true;
}

python

def solution(pattern, s):
    if not pattern and not s:
        return True
    words = s.split(' ')
    if len(pattern) != len(words):
        return False
    p2w = {}
    w2p = {}
    for ch, w in zip(pattern, words):
        if ch in p2w and p2w[ch] != w:
            return False
        if w in w2p and w2p[w] != ch:
            return False
        p2w[ch] = w
        w2p[w] = ch
    return True

rust

use std::collections::HashMap;
fn solution(pattern: &str, s: &str) -> bool {
    if pattern.is_empty() && s.is_empty() { return true; }
    let words: Vec<&str> = s.split(' ').collect();
    if pattern.len() != words.len() { return false; }
    let mut p2w: HashMap<char, &str> = HashMap::new();
    let mut w2p: HashMap<&str, char> = HashMap::new();
    for (i, ch) in pattern.chars().enumerate() {
        let w = words[i];
        if let Some(&cw) = p2w.get(&ch) { if cw != w { return false; } }
        if let Some(&pc) = w2p.get(w) { if pc != ch { return false; } }
        p2w.insert(ch, w);
        w2p.insert(w, ch);
    }
    true
}

typescript

function solution(pattern: string, s: string): boolean {
    if (!pattern && !s) return true;
    var words = s.split(' ');
    if (pattern.length !== words.length) return false;
    var p2w: any = {}, w2p: any = {};
    for (var i = 0; i < pattern.length; i++) {
        var ch = pattern.charAt(i);
        var w = words[i];
        if (p2w[ch] && p2w[ch] !== w) return false;
        if (w2p[w] && w2p[w] !== ch) return false;
        p2w[ch] = w;
        w2p[w] = ch;
    }
    return true;
}

Related Hash Table Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Word Pattern

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Hash Table Challenges

Duplicate Indices Map

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Majority Element

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.