> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Word Pattern II Python Solution with Tests

> Tested Python solution for LeetCode 291 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 291, [Medium](/catalog/medium). Topics: [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking). [View on LeetCode](https://leetcode.com/problems/word-pattern-ii/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 291   # by problem number
lcpy gen -s word_pattern_ii   # by problem name
```

## 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, and no character maps to two different strings.

### Examples

```
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"
```

```
Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"
```

```
Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false
```

### Constraints

* `1 <= pattern.length, s.length <= 20`
* `pattern` and `s` consist of only lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/word_pattern_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/word_pattern_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^m) where n = len(s), m = len(pattern)
    # Space: O(n + m)
    def word_pattern_match(self, pattern: str, s: str) -> bool:
        char_to_word: dict[str, str] = {}
        used: set[str] = set()

        def backtrack(p_idx: int, s_idx: int) -> bool:
            if p_idx == len(pattern) and s_idx == len(s):
                return True
            if p_idx == len(pattern) or s_idx == len(s):
                return False
            char = pattern[p_idx]
            if char in char_to_word:
                word = char_to_word[char]
                if not s.startswith(word, s_idx):
                    return False
                return backtrack(p_idx + 1, s_idx + len(word))
            for end in range(s_idx + 1, len(s) + 1):
                word = s[s_idx:end]
                if word in used:
                    continue
                char_to_word[char] = word
                used.add(word)
                if backtrack(p_idx + 1, end):
                    return True
                del char_to_word[char]
                used.remove(word)
            return False

        return backtrack(0, 0)
```

## Complexity

| Time | Space |
| - | - |
| O(n^m) where n = len(s), m = len(pattern) | O(n + m) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.