# LeetCode 291: Word Pattern II

## Problem Restatement

We are given:

```python
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:

| Rule | Meaning |
|---|---|
| One character maps to one substring | The same pattern character must always use the same substring |
| One substring maps to one character | Two different pattern characters cannot use the same substring |
| Full match | All of `pattern` and all of `s` must be consumed |

For example:

```python
pattern = "abab"
s = "redblueredblue"
```

This is valid with:

```python
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

| Item | Meaning |
|---|---|
| Input | String `pattern`, string `s` |
| Output | `True` if `s` matches `pattern`, otherwise `False` |
| Mapping | Pattern character to non-empty substring |
| Constraint | No two characters may map to the same substring |
| Constraint | One character cannot map to different substrings |

Function shape:

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

## Examples

For:

```python
pattern = "abab"
s = "redblueredblue"
```

Return:

```python
True
```

because:

```python
a -> "red"
b -> "blue"
```

For:

```python
pattern = "aaaa"
s = "asdasdasdasd"
```

Return:

```python
True
```

because:

```python
a -> "asd"
```

For:

```python
pattern = "aabb"
s = "xyzabcxzyabc"
```

Return:

```python
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:

```python
"dog cat cat dog"
```

So each pattern character matched one known word.

Here there are no separators.

For:

```python
s = "redblueredblue"
```

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

```python
"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:

| Variable | Meaning |
|---|---|
| `i` | Current index in `pattern` |
| `j` | Current index in `s` |

Also keep:

| Structure | Meaning |
|---|---|
| `char_to_str` | Current mapping from pattern character to substring |
| `used` | Substrings already assigned to some character |

At each step, look at:

```python
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:

```python
dfs(i, j)
```

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

Base case:

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

If only one side is finished:

```python
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.

```python
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:

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

If the character is unmapped, try every substring:

```python
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | Exponential | The search tries many substring assignments |
| Space | `O(m + n)` | Recursion stack, mapping, and used substrings |

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

## Implementation

```python
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:

```python
char_to_str = {}
```

We also keep all substrings already used:

```python
used = set()
```

This prevents two characters from sharing the same substring.

The DFS starts at the beginning of both strings:

```python
return dfs(0, 0)
```

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

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

If only one side ends, the match fails:

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

The pruning condition removes impossible paths:

```python
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:

```python
if char in char_to_str:
```

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

```python
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:

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

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

```python
if word in used:
    continue
```

Then we assign, recurse, and backtrack:

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

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

used.remove(word)
del char_to_str[char]
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"abab"`, `"redblueredblue"` | Standard valid alternating mapping |
| `"aaaa"`, `"asdasdasdasd"` | One character maps to repeated substring |
| `"aabb"`, `"xyzabcxzyabc"` | Standard invalid case |
| `"ab"`, `"aa"` | Two characters cannot both map to `"a"` |
| `"ab"`, `"redblue"` | Simple two-character valid mapping |
| `"aba"`, `"redbluered"` | Same character reused consistently |
| `"aba"`, `"redblueblue"` | Same character would need inconsistent mappings |