Word Pattern - Practice Coding Problems

Word Pattern - 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

Input & Output

Example 1 — Basic Pattern Match

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

› Output: true

💡 Note: Pattern 'a' maps to 'dog' and 'b' maps to 'cat'. The sequence abba becomes dog-cat-cat-dog, which matches the input string exactly.

Example 2 — Bijection Violation

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

› Output: false

💡 Note: Pattern 'a' first maps to 'dog', but then would need to map to 'fish' in the last position. This violates the bijection requirement.

Example 3 — Length Mismatch

$ Input: pattern = "aaaa", s = "dog dog dog"

› Output: false

💡 Note: Pattern has 4 characters but string has only 3 words. They must have equal length for a valid pattern match.

Constraints

1 ≤ pattern.length ≤ 300
pattern contains only lower-case English letters
1 ≤ s.length ≤ 3000
s contains only lowercase English letters and spaces ' '

Visualization

Tap to expand

Understanding the Visualization

Input

Pattern 'abba' and string 'dog cat cat dog'

Mapping

Each pattern character maps to exactly one unique word

Verification

Check if mapping is consistent and bijective

Key Takeaway

🎯 Key Insight: Use two hash maps to ensure bijective mapping - each character maps to exactly one word and each word maps to exactly one character

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use two hash maps to maintain a bijection between pattern characters and words. The optimal approach checks both directions (char→word and word→char) in a single pass. Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with String Generation	O(n! × m)	O(n × m)	Try all possible word assignments to pattern characters
Two Hash Maps (Bidirectional Mapping)	O(n)	O(k)	Use two hash maps to ensure one-to-one mapping between characters and words

Brute Force with String Generation — Algorithm Steps

Split string into words
Generate all possible character-to-word mappings
For each mapping, reconstruct pattern and compare

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Words

Split string into individual words

Generate Mappings

Try all possible character-to-word assignments

Verify

Check if any mapping produces correct pattern

Code -

solution.c — C

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

bool tryMapping(char* pattern, char words[][100], int wordCount, 
               char chars[], int charCount, char availableWords[][100], 
               int availableCount, char mapping[][100], int index) {
    if (index == charCount) {
        for (int i = 0; i < strlen(pattern); i++) {
            bool found = false;
            for (int j = 0; j < charCount; j++) {
                if (chars[j] == pattern[i]) {
                    if (strcmp(mapping[j], words[i]) != 0) {
                        return false;
                    }
                    found = true;
                    break;
                }
            }
            if (!found) return false;
        }
        return true;
    }
    
    for (int i = 0; i < availableCount; i++) {
        strcpy(mapping[index], availableWords[i]);
        
        char newAvailable[100][100];
        int newCount = 0;
        for (int j = 0; j < availableCount; j++) {
            if (j != i) {
                strcpy(newAvailable[newCount], availableWords[j]);
                newCount++;
            }
        }
        
        if (tryMapping(pattern, words, wordCount, chars, charCount, 
                      newAvailable, newCount, mapping, index + 1)) {
            return true;
        }
    }
    
    return false;
}

bool solution(char* pattern, char* s) {
    char words[100][100];
    int wordCount = 0;
    
    char* token = strtok(s, " ");
    while (token != NULL && wordCount < 100) {
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, " ");
    }
    
    if (strlen(pattern) != wordCount) {
        return false;
    }
    
    char uniqueWords[100][100];
    int uniqueWordCount = 0;
    char uniqueChars[100];
    int uniqueCharCount = 0;
    
    // Find unique words
    for (int i = 0; i < wordCount; i++) {
        bool found = false;
        for (int j = 0; j < uniqueWordCount; j++) {
            if (strcmp(words[i], uniqueWords[j]) == 0) {
                found = true;
                break;
            }
        }
        if (!found) {
            strcpy(uniqueWords[uniqueWordCount], words[i]);
            uniqueWordCount++;
        }
    }
    
    // Find unique chars
    for (int i = 0; i < strlen(pattern); i++) {
        bool found = false;
        for (int j = 0; j < uniqueCharCount; j++) {
            if (pattern[i] == uniqueChars[j]) {
                found = true;
                break;
            }
        }
        if (!found) {
            uniqueChars[uniqueCharCount] = pattern[i];
            uniqueCharCount++;
        }
    }
    
    if (uniqueCharCount > uniqueWordCount) {
        return false;
    }
    
    char mapping[100][100];
    return tryMapping(pattern, words, wordCount, uniqueChars, uniqueCharCount, 
                     uniqueWords, uniqueWordCount, mapping, 0);
}

int main() {
    char pattern[1000], s[10000];
    fgets(pattern, sizeof(pattern), stdin);
    fgets(s, sizeof(s), stdin);
    
    // Remove newlines
    pattern[strcspn(pattern, "\n")] = 0;
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(pattern, s);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × m)

n! permutations of word assignments, each taking O(m) to verify

⚠ Quadratic Growth

Space Complexity

O(n × m)

Storage for all permutations and word mappings

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with String Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler