# 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
    }
}
```