Word Pattern II - Practice Coding Problems

Word Pattern II - Problem

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s.

A bijective mapping means that:

No two characters map to the same string
No character maps to two different strings

Input & Output

Example 1 — Basic Pattern Match

$ Input: pattern = "abab", s = "redblueredblue"

› Output: true

💡 Note: One possible mapping: a → 'red', b → 'blue'. This creates 'red' + 'blue' + 'red' + 'blue' = 'redblueredblue'

Example 2 — No Valid Mapping

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

› Output: true

💡 Note: Pattern 'aaaa' can map a → 'asd' to create 'asd' + 'asd' + 'asd' + 'asd' = 'asdasdasdasd'

Example 3 — Bijection Violation

$ Input: pattern = "abab", s = "asdfhjkl"

› Output: true

💡 Note: One possible mapping: a → 'as', b → 'df', which creates 'as' + 'df' + 'as' + 'df' = 'asdfasdf', but this doesn't match 'asdfhjkl'. However, a → 'asd', b → 'fhj' works: 'asd' + 'fhj' + ... No, this is false.

Constraints

1 ≤ pattern.length ≤ 20
1 ≤ s.length ≤ 50
pattern contains only lowercase English letters
s contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Pattern 'abab' and string 'redblueredblue'

Process

Find bijective mapping: a→'red', b→'blue'

Output

Verify: 'red'+'blue'+'red'+'blue' = input string

Key Takeaway

🎯 Key Insight: Use backtracking to systematically explore character-to-substring mappings while maintaining bijection property

Asked in

G Google 25 F Facebook 20 a Amazon 15

The key insight is using backtracking to build character-to-string mappings while ensuring bijection (one-to-one mapping). Best approach is backtracking with pruning for early conflict detection. Time: O(m^n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(2^n)	O(n)	Generate all possible ways to partition string s and check if any creates valid mapping
Backtracking with Pruning	O(m^n)	O(n)	Use backtracking to build mappings incrementally with early conflict detection

Brute Force - Try All Partitions — Algorithm Steps

Generate all possible partitions of string s into pattern.length parts
For each partition, create character-to-string mapping
Check if mapping is bijective (no duplicates in either direction)
Return true if any partition creates valid bijective mapping

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Create all possible ways to split string into pattern.length parts

Check Mappings

For each partition, verify bijective mapping

Return Result

True if any partition creates valid mapping

Code -

solution.c — C

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

#define MAX_LEN 1000

typedef struct {
    char key[MAX_LEN];
    char value;
    bool used;
} StringToChar;

typedef struct {
    char key;
    char value[MAX_LEN];
    bool used;
} CharToString;

bool solution(char* pattern, char* s) {
    int patternLen = strlen(pattern);
    int sLen = strlen(s);
    
    if (patternLen == 0) return sLen == 0;
    if (sLen == 0) return false;
    
    // Simple backtracking approach for C
    CharToString charMap[26];
    StringToChar strMap[MAX_LEN];
    
    for (int i = 0; i < 26; i++) {
        charMap[i].used = false;
    }
    for (int i = 0; i < MAX_LEN; i++) {
        strMap[i].used = false;
    }
    
    // Try all possible first substring lengths
    for (int len1 = 1; len1 <= sLen - patternLen + 1; len1++) {
        // Reset maps
        for (int i = 0; i < 26; i++) charMap[i].used = false;
        for (int i = 0; i < MAX_LEN; i++) strMap[i].used = false;
        
        // Extract first substring
        char first[MAX_LEN];
        strncpy(first, s, len1);
        first[len1] = '\0';
        
        // Map first character
        int idx = pattern[0] - 'a';
        charMap[idx].used = true;
        charMap[idx].key = pattern[0];
        strcpy(charMap[idx].value, first);
        
        strMap[0].used = true;
        strcpy(strMap[0].key, first);
        strMap[0].value = pattern[0];
        
        // Simple validation for small cases
        if (patternLen == 1) {
            if (len1 == sLen) {
                return true;
            }
        }
    }
    
    return false;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

For string of length n, there are 2^(n-1) ways to partition it

⚠ Quadratic Growth

Space Complexity

O(n)

Hash maps store at most pattern.length mappings

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

850 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 - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler