290. Word Pattern - Solution & Explanation

Q: Is Word Pattern easy or hard?

Word Pattern is classified as an Easy problem on LeetCode with an acceptance rate around 44%. The challenge mainly involves recognizing the need for a bijection and implementing it correctly using hash maps.

Q: Word Pattern Python/Java solution

Both Python and Java implementations typically use hash maps (Python dictionaries or Java HashMap). The algorithm iterates through the pattern and the word array simultaneously, validating that mappings remain consistent throughout the traversal.

Q: How to solve Word Pattern in O(n)?

Split the input sentence into words and iterate through the pattern and word list together. Use a hash map to track the mapping between pattern characters and words while verifying the reverse mapping as well. Each step performs constant-time checks, giving an overall O(n) time complexity.

Q: What is the best approach for Word Pattern?

The hash map mapping approach is the most widely used solution. It maintains two mappings: pattern character to word and word to pattern character, ensuring a one-to-one relationship. Each lookup is O(1), so the overall time complexity is O(n) with O(n) space.

Q: Is Word Pattern asked at Google/Amazon/Meta?

Word Pattern is a common interview-style problem focused on hash tables and string mapping. Variants of this question have appeared in interviews at companies like Amazon and Google because it tests understanding of bijection constraints and hash map usage.

Q: What data structure is used in Word Pattern?

Hash tables are the primary data structure used in this problem. They allow constant-time lookups to track mappings between pattern characters and words or to store last-seen indices for each element.

Q: What is the time complexity of Word Pattern?

The optimal solutions run in O(n) time, where n is the number of words in the input sentence. Each character and word pair is processed once with constant-time hash lookups. Space complexity is O(n) due to the hash maps storing mappings or last-seen indices.

The problem

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

Example 1:

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

Output: true

Explanation:

The bijection can be established as:

'a' maps to "dog".
'b' maps to "cat".

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 <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Approach overview

Problem Overview: You are given a pattern string and a space-separated sentence. The task is to determine whether the sentence follows the same pattern. Each character in the pattern must map to exactly one word in the sentence, and no two characters can map to the same word.

This is a classic bijection validation problem. You must ensure a one-to-one relationship between pattern characters and words. Problems like this frequently rely on hash table lookups and efficient string processing.

Approach 1: Hash Map Mapping (O(n) time, O(n) space)

The most direct solution uses two hash maps to enforce a bijection between pattern characters and words. Split the sentence into words, then iterate through both the pattern and word list simultaneously. One map stores char → word and another stores word → char. During iteration, verify that existing mappings remain consistent. If a mismatch appears, return false immediately. Hash lookups make each check constant time, so the overall runtime is O(n) where n is the number of words. This approach is easy to reason about and mirrors how interviewers expect you to validate one-to-one mappings.

Approach 2: Index Mapping (O(n) time, O(n) space)

Instead of storing explicit mappings, track the last index where each pattern character and word appeared. Use two maps: char → last index and word → last index. As you iterate through the sequence, compare the stored indices for the current character and word. If they differ, the pattern relationship is broken. If they match, update both with the current index. This works because valid pairs must always appear at the same positions in their respective sequences. The method still runs in O(n) time with O(n) space but avoids storing full string mappings.

Recommended for interviews: The hash map mapping approach is the most common answer because it clearly demonstrates understanding of bijection constraints. Interviewers expect candidates to enforce both directions of the mapping. The index mapping technique is a clever alternative that reduces conceptual overhead once you recognize the pattern of comparing last-seen indices.

Approach 1: Approach 1: Hash Map Mapping

This approach uses two hash maps (dictionaries) to establish bijective mappings between characters in the pattern and words in the string. One map tracks the character to word mapping, while the other tracks word to character mapping. During iteration, we update or check both maps to ensure the bijection property holds.

Python

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words):
        return False
    char_to_word = {}
    word_to_char = {}
    for char, word in zip(pattern, words):
        if char in char_to_word and char_to_word[char] != word:
            return False
        if word in word_to_char and word_to_char[word] != char:
            return False
        char_to_word[char] = word
        word_to_char[word] = char
    return True

print(wordPattern("abba", "dog cat cat dog"))  # True

Java

import java.util.HashMap;

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

    public static void main(String[] args) {
        System.out.println(wordPattern("abba", "dog cat cat dog"));
    }
}

C++

#include <iostream>
#include <sstream>
#include <unordered_map>
#include <string>
using namespace std;

bool wordPattern(string pattern, string s) {
    unordered_map<char, string> charToWord;
    unordered_map<string, char> wordToChar;
    stringstream ss(s);
    string word;
    size_t i = 0;
    while (ss >> word) {
        if (i == pattern.length()) return false;
        char c = pattern[i++];
        if (charToWord.count(c) && charToWord[c] != word) return false;
        if (wordToChar.count(word) && wordToChar[word] != c) return false;
        charToWord[c] = word;
        wordToChar[word] = c;
    }
    return i == pattern.length();
}

int main() {
    cout << (wordPattern("abba", "dog cat cat dog") ? "True" : "False") << endl;
    return 0;
}

JavaScript

function wordPattern(pattern, s) {
    const words = s.split(' ');
    if (pattern.length !== words.length) return false;

    const charToWord = new Map();
    const wordToChar = new Map();

    for (let i = 0; i < pattern.length; i++) {
        const char = pattern[i];
        const word = words[i];

        if (charToWord.has(char) && charToWord.get(char) !== word) return false;
        if (wordToChar.has(word) && wordToChar.get(word) !== char) return false;

        charToWord.set(char, word);
        wordToChar.set(word, char);
    }
    return true;
}

console.log(wordPattern("abba", "dog cat cat dog")); // true

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>

#define HASH_SIZE 128

unsigned int hash(const char* s) {
    unsigned int hash = 0;
    while (*s) {
        hash = (hash << 5) + *s++;
    }
    return hash % HASH_SIZE;
}

bool wordPattern(char* pattern, char* s) {
    char* wordMap[HASH_SIZE] = {0};
    char* reverseMap[HASH_SIZE] = {0};
    char word[101];
    int wordLen = 0;
    
    int wordIndex = 0;
    char* p = pattern;
    while (*p) {
        while (*s && isspace(*s)) s++; // skip spaces

        wordLen = 0;
        while (*s && !isspace(*s)) {
            word[wordLen++] = *s++;
        }
        word[wordLen] = '\0';

        if (wordLen == 0) return false;

        unsigned int hashIndex = hash(word);
        if (!wordMap[*p]) {
            // new pattern character
            if (reverseMap[hashIndex]) {
                if (strcmp(reverseMap[hashIndex], &*p) != 0) return false;
            } else {
                reverseMap[hashIndex] = &*p;
            }
            wordMap[*p] = strdup(word);
        } else if (strcmp(wordMap[*p], word) != 0) {
            return false;
        }
        p++;
    }
    return *s == '\0' && *p == '\0';
}

int main() {
    printf("%d", wordPattern("abba", "dog cat cat dog")); // 1
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public bool WordPattern(string pattern, string s) {
        string[] words = s.Split(' ');
        if (pattern.Length != words.Length) return false;

        Dictionary<char, string> charToWord = new Dictionary<char, string>();
        Dictionary<string, char> wordToChar = new Dictionary<string, char>();

        for (int i = 0; i < pattern.Length; i++) {
            char c = pattern[i];
            string word = words[i];

            if (charToWord.ContainsKey(c) && charToWord[c] != word) return false;
            if (wordToChar.ContainsKey(word) && wordToChar[word] != c) return false;

            charToWord[c] = word;
            wordToChar[word] = c;
        }

        return true;
    }

    static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.WordPattern("abba", "dog cat cat dog"));
    }
}

This Python code uses two dictionaries to track mappings between pattern characters and words. The split words get compared with the characters, with validations set to ensure correct relations in both mappings.

Complexity

Time Complexity: O(n + m).
Space Complexity: O(n + m).

Try this approach in the editor

Approach 2: Approach 2: Index Mapping

The index mapping approach ensures that the last seen indexes of each character in the pattern and each word from s match. By tracking their last occurrences, you can simplify identifying mismatched patterns in linear time.

Python

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words):
        return False
    index_map = {}
    for i, (c, word) in enumerate(zip(pattern, words)):
        if index_map.setdefault(c, i) != index_map.setdefault(word, i):
            return False
    return True

print(wordPattern("abba", "dog cat cat dog"))  # True

Java

import java.util.HashMap;

public class Main {
    public static boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) return false;
        HashMap<Object, Integer> indexMap = new HashMap<>();
        for (Integer i = 0; i < pattern.length(); ++i) {
            if (indexMap.put(pattern.charAt(i), i) != indexMap.put(words[i], i))
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(wordPattern("abba", "dog cat cat dog"));
    }
}

C++

#include <iostream>
#include <sstream>
#include <unordered_map>
#include <string>
using namespace std;

bool wordPattern(string pattern, string s) {
    unordered_map<char, int> charIndexMap;
    unordered_map<string, int> wordIndexMap;
    istringstream iss(s);
    string word;
    int index = 0;
    for (string::size_type i = 0; i != pattern.size(); ++i) {
        if (!(iss >> word)) return false;
        if (charIndexMap[pattern[i]] != wordIndexMap[word]) return false;
        charIndexMap[pattern[i]] = wordIndexMap[word] = i + 1;
    }
    return !(iss >> word);
}

int main() {
    cout << (wordPattern("abba", "dog cat cat dog") ? "True" : "False") << endl;
    return 0;
}

JavaScript

function wordPattern(pattern, s) {
    const words = s.split(' ');
    if (words.length !== pattern.length) return false;
    const indexMap = new Map();
    for (let i = 0; i < pattern.length; ++i) {
        const patternCharKey = `p:${pattern[i]}`;
        const wordKey = `w:${words[i]}`;

        if (!indexMap.has(patternCharKey)) indexMap.set(patternCharKey, i);
        if (!indexMap.has(wordKey)) indexMap.set(wordKey, i);

        if (indexMap.get(patternCharKey) !== indexMap.get(wordKey)) return false;
    }
    return true;
}

console.log(wordPattern("abba", "dog cat cat dog")); // true

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

bool wordPattern(char* pattern, char* s) {
    char words[300][100];
    int n = 0;
    char *word = strtok(s, " ");
    while (word != NULL) {
        strcpy(words[n++], word);
        word = strtok(NULL, " ");
    }
    
    if (strlen(pattern) != n) return false;

    int pIdx[256] = {0};
    int wIdx[300][100] = {0};

    for (int i = 0; i < n; ++i) {
        if (pIdx[(int)pattern[i]] != wIdx[words[i][0]]) return false;
        pIdx[(int)pattern[i]] = wIdx[words[i][0]] = i + 1;
    }
    return true;
}

int main() {
    printf("%d", wordPattern("abba", "dog cat cat dog")); // 1 (true)
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public bool WordPattern(string pattern, string s) {
        string[] words = s.Split(' ');
        if (pattern.Length != words.Length) return false;

        Dictionary<object, int> indexMap = new Dictionary<object, int>();

        for (int i = 0; i < pattern.Length; i++) {
            if (!indexMap.TryAdd(pattern[i], i) && indexMap[pattern[i]] != i)
                return false;
            if (!indexMap.TryAdd(words[i], i) && indexMap[words[i]] != i)
                return false;
        }

        return true;
    }

    static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.WordPattern("abba", "dog cat cat dog"));
    }
}

Utilizing a single dictionary in Python solves this flexible index approach. Tuple-wise assignments into and comparisons with this 'index_map' ensure mappings happen consistently, allowing easy conflict verification.

Complexity

Time Complexity: O(n + m)
Space Complexity: O(n + m)

Try this approach in the editor

Approach 3: Hash Table

First, we split the string s into a word array ws with spaces. If the length of pattern and ws is not equal, return false directly. Otherwise, we use two hash tables d_1 and d_2 to record the correspondence between each character and word in pattern and ws.

Then, we traverse pattern and ws. For each character a and word b, if there is a mapping for a in d_1, and the mapped word is not b, or there is a mapping for b in d_2, and the mapped character is not a, return false. Otherwise, we add the mapping of a and b to d_1 and d_2 respectively.

After the traversal, return true.

The time complexity is O(m + n) and the space complexity is O(m + n). Here m and n are the length of pattern and string s.

TypeScript

function wordPattern(pattern: string, s: string): boolean {
    const ws = s.split(' ');
    if (pattern.length !== ws.length) {
        return false;
    }
    const d1 = new Map<string, string>();
    const d2 = new Map<string, string>();
    for (let i = 0; i < pattern.length; ++i) {
        const a = pattern[i];
        const b = ws[i];
        if (d1.has(a) && d1.get(a) !== b) {
            return false;
        }
        if (d2.has(b) && d2.get(b) !== a) {
            return false;
        }
        d1.set(a, b);
        d2.set(b, a);
    }
    return true;
}

func wordPattern(pattern string, s string) bool {
	ws := strings.Split(s, " ")
	if len(ws) != len(pattern) {
		return false
	}
	d1 := map[rune]string{}
	d2 := map[string]rune{}
	for i, a := range pattern {
		b := ws[i]
		if v, ok := d1[a]; ok && v != b {
			return false
		}
		if v, ok := d2[b]; ok && v != a {
			return false
		}
		d1[a] = b
		d2[b] = a
	}
	return true
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn word_pattern(pattern: String, s: String) -> bool {
        let cs1: Vec<char> = pattern.chars().collect();
        let cs2: Vec<&str> = s.split_whitespace().collect();
        let n = cs1.len();
        if n != cs2.len() {
            return false;
        }
        let mut map1 = HashMap::new();
        let mut map2 = HashMap::new();
        for i in 0..n {
            let c = cs1[i];
            let s = cs2[i];
            if !map1.contains_key(&c) {
                map1.insert(c, i);
            }
            if !map2.contains_key(&s) {
                map2.insert(s, i);
            }
            if map1.get(&c) != map2.get(&s) {
                return false;
            }
        }
        true
    }
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function wordPattern(pattern: string, s: string): boolean {
    const hash: Record<string, string> = Object.create(null);
    const arr = s.split(/\s+/);

    if (pattern.length !== arr.length || new Set(pattern).size !== new Set(arr).size) {
        return false;
    }

    for (let i = 0; i < pattern.length; i++) {
        hash[pattern[i]] ??= arr[i];
        if (hash[pattern[i]] !== arr[i]) {
            return false;
        }
    }

    return true;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Hash Map Mapping	Time Complexity: O(n + m). Space Complexity: O(n + m).
Approach 2: Index Mapping	Time Complexity: O(n + m) Space Complexity: O(n + m)
Hash Table	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Hash Map Mapping	O(n)	O(n)	General case when validating one-to-one mapping between two sequences
Index Mapping	O(n)	O(n)	When you want a concise solution using last-seen index comparisons

Frequently asked questions

Is Word Pattern easy or hard?

Word Pattern is classified as an Easy problem on LeetCode with an acceptance rate around 44%. The challenge mainly involves recognizing the need for a bijection and implementing it correctly using hash maps.

Word Pattern Python/Java solution

Both Python and Java implementations typically use hash maps (Python dictionaries or Java HashMap). The algorithm iterates through the pattern and the word array simultaneously, validating that mappings remain consistent throughout the traversal.

How to solve Word Pattern in O(n)?

Split the input sentence into words and iterate through the pattern and word list together. Use a hash map to track the mapping between pattern characters and words while verifying the reverse mapping as well. Each step performs constant-time checks, giving an overall O(n) time complexity.

What is the best approach for Word Pattern?

The hash map mapping approach is the most widely used solution. It maintains two mappings: pattern character to word and word to pattern character, ensuring a one-to-one relationship. Each lookup is O(1), so the overall time complexity is O(n) with O(n) space.

Is Word Pattern asked at Google/Amazon/Meta?

Word Pattern is a common interview-style problem focused on hash tables and string mapping. Variants of this question have appeared in interviews at companies like Amazon and Google because it tests understanding of bijection constraints and hash map usage.

What data structure is used in Word Pattern?

Hash tables are the primary data structure used in this problem. They allow constant-time lookups to track mappings between pattern characters and words or to store last-seen indices for each element.

What is the time complexity of Word Pattern?

The optimal solutions run in O(n) time, where n is the number of words in the input sentence. Each character and word pair is processed once with constant-time hash lookups. Space complexity is O(n) due to the hash maps storing mappings or last-seen indices.

Word Pattern solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Hash Map Mapping

Approach 2: Approach 2: Index Mapping

Approach 3: Hash Table

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Word Pattern solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Hash Map Mapping

Approach 2: Approach 2: Index Mapping

Approach 3: Hash Table

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems