> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0291-word-pattern-ii.md).

# 0291. Word Pattern II

<https://leetcode.com/problems/word-pattern-ii>

## Description

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

**Example 1:**

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

**Example 2:**

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

**Example 3:**

```
**Input:** pattern = "abab", s = "asdasdasdasd"
**Output:** true
**Explanation:** One possible mapping is as follows:
'a' -> "a"
'b' -> "sdasd"
Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection.
```

**Example 4:**

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

**Constraints:**

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

## ac

```java
class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();

        return backtrack(pattern, 0, str, 0, map, set);
    }
    private boolean backtrack(String pattern, int pstart, String str, int sstart, Map<Character, String> map, Set<String> set) {
        // exit, reach the end
        if (pstart >= pattern.length() || sstart >= str.length()) {
            return pstart == pattern.length() && sstart == str.length(); // both should reach the end to say true
        }

        char curr = pattern.charAt(pstart);
        // in map, seen before
        if (map.containsKey(curr)) {
            String prev = map.get(curr);

            if (!str.startsWith(prev, sstart)) return false; // dont' match previous result, start over

            // matach, move on the next
            return backtrack(pattern, pstart+1, str, sstart + prev.length(), map, set);
        } 

        // not in map, try different strings in str
        for (int i = sstart; i < str.length(); i++) {
            String candidate = str.substring(sstart, i + 1);
            if (set.contains(candidate)) continue; // this string used by others before, skip it.
            map.put(curr, candidate);
            set.add(candidate);

            if (backtrack(pattern, pstart+1, str, i + 1, map, set)) return true;

            map.remove(curr);
            set.remove(candidate);
        }

        return false; // cant match, false
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0291-word-pattern-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.