LeetCode 291: Word Pattern II

Problem Restatement

We are given:

pattern
s

We need to check whether s follows pattern.

Each character in pattern must map to a non-empty substring of s.

The mapping must be bijective:

For example:

pattern = "abab"
s = "redblueredblue"

This is valid with:

a -> "red"
b -> "blue"

The official statement defines the task as finding whether there is a bijective mapping from pattern characters to non-empty strings so that replacing each pattern character reconstructs s.

Input and Output

Function shape:

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        ...

Examples

For:

pattern = "abab"
s = "redblueredblue"

Return:

True

because:

a -> "red"
b -> "blue"

For:

pattern = "aaaa"
s = "asdasdasdasd"

Return:

True

because:

a -> "asd"

For:

pattern = "aabb"
s = "xyzabcxzyabc"

Return:

False

There is no bijective mapping that reconstructs the whole string. These are the examples listed in the source statement.

First Thought: Try Fixed Word Splitting

LeetCode 290 had spaces between words:

"dog cat cat dog"

So each pattern character matched one known word.

Here there are no separators.

For:

s = "redblueredblue"

we do not know whether the first pattern character should map to:

"r"
"re"
"red"
"redb"
...

So we must try possible substring lengths.

That naturally leads to backtracking.

Key Insight

Use depth-first search with two positions:

Also keep:

At each step, look at:

c = pattern[i]

If c already has a mapping, the next part of s must start with that mapped substring.

If it does, continue.

If it does not, this path fails.

If c has no mapping yet, try every possible non-empty substring starting at j.

For each candidate substring:

1. Skip it if another character already uses it.
2. Assign it to c.
3. Recurse.
4. Remove the assignment if recursion fails.

Algorithm

Define:

dfs(i, j)

where i is the pattern index and j is the string index.

Base case:

if i == len(pattern) and j == len(s):
    return True

If only one side is finished:

return False

Pruning:

If the remaining string is shorter than the remaining pattern length, return False, because each remaining pattern character needs at least one character.

if len(s) - j < len(pattern) - i:
    return False

Then process pattern[i].

If it already maps to word, check whether s starts with word at position j.

If yes, recurse with:

dfs(i + 1, j + len(word))

If the character is unmapped, try every substring:

s[j:end]

where end goes from j + 1 to len(s).

Correctness

The DFS explores every possible assignment of non-empty substrings to pattern characters.

When a pattern character already has a mapping, the algorithm accepts only the exact same substring at the current string position. This enforces consistency.

When a pattern character has no mapping, the algorithm tries every possible non-empty substring starting at the current string position. This covers all valid choices.

The used set prevents two different pattern characters from mapping to the same substring, which enforces the bijection requirement.

The recursion succeeds only when both pattern and s are fully consumed. Therefore partial matches are rejected.

Since every valid mapping corresponds to exactly one path in the DFS, and invalid paths are rejected as soon as they violate consistency or bijection, the algorithm returns True exactly when a valid full mapping exists.

Complexity

Let:

n = len(s)
m = len(pattern)

The constraints are small, with pattern.length and s.length at most 20, so backtracking is acceptable.

Implementation

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        char_to_str = {}
        used = set()

        def dfs(i: int, j: int) -> bool:
            if i == len(pattern) and j == len(s):
                return True

            if i == len(pattern) or j == len(s):
                return False

            if len(s) - j < len(pattern) - i:
                return False

            char = pattern[i]

            if char in char_to_str:
                word = char_to_str[char]

                if not s.startswith(word, j):
                    return False

                return dfs(i + 1, j + len(word))

            for end in range(j + 1, len(s) + 1):
                word = s[j:end]

                if word in used:
                    continue

                char_to_str[char] = word
                used.add(word)

                if dfs(i + 1, end):
                    return True

                used.remove(word)
                del char_to_str[char]

            return False

        return dfs(0, 0)

Code Explanation

We keep the current character-to-substring mapping:

char_to_str = {}

We also keep all substrings already used:

used = set()

This prevents two characters from sharing the same substring.

The DFS starts at the beginning of both strings:

return dfs(0, 0)

If both indices reach the end, we found a full match:

if i == len(pattern) and j == len(s):
    return True

If only one side ends, the match fails:

if i == len(pattern) or j == len(s):
    return False

The pruning condition removes impossible paths:

if len(s) - j < len(pattern) - i:
    return False

Each remaining pattern character needs at least one string character.

If the current pattern character already has a mapping:

if char in char_to_str:

then the next part of s must match that exact substring:

if not s.startswith(word, j):
    return False

If it matches, we consume that substring and continue.

If the character has no mapping yet, we try every possible non-empty substring:

for end in range(j + 1, len(s) + 1):

Before trying a substring, we check whether another character already uses it:

if word in used:
    continue

Then we assign, recurse, and backtrack:

char_to_str[char] = word
used.add(word)

if dfs(i + 1, end):
    return True

used.remove(word)
del char_to_str[char]

Testing

def test_word_pattern_match():
    s = Solution()

    assert s.wordPatternMatch("abab", "redblueredblue") is True
    assert s.wordPatternMatch("aaaa", "asdasdasdasd") is True
    assert s.wordPatternMatch("aabb", "xyzabcxzyabc") is False
    assert s.wordPatternMatch("ab", "aa") is False
    assert s.wordPatternMatch("ab", "redblue") is True
    assert s.wordPatternMatch("aba", "redbluered") is True
    assert s.wordPatternMatch("aba", "redblueblue") is False

    print("all tests passed")

test_word_pattern_match()

Test meaning: