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

# 291    Word Pattern II

## 291. [Word Pattern II](https://leetcode.com/problems/word-pattern-ii/description/)

## 1. Question

Given a`pattern`and a string`str`, find if`str`follows the same pattern.

Here **follow** means a full match, such that there is a bijection between a letter in`pattern`and a **non-empty** substring in`str`.

**Examples:**

1. pattern =`"abab"`, str =`"redblueredblue"`should return true.
2. pattern =`"aaaa"`, str =`"asdasdasdasd"`should return true.
3. pattern =`"aabb"`, str =`"xyzabcxzyabc"`should return false.

**Notes:**\
You may assume both`pattern`and`str`contains only lowercase letters.

## 2. Implementation

**(1) Backtracking**

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

    public boolean isMatched(String pattern, int patternIndex, String str, int strIndex, Set<String> set, Map<Character, String> map) {
        if (patternIndex == pattern.length() && strIndex == str.length()) {
            return true;
        }

        // 没有足够的部分完成匹配
        if (patternIndex == pattern.length() || strIndex == str.length() 
            || str.length() - strIndex < pattern.length() - patternIndex) {
            return false;
        }

        char c = pattern.charAt(patternIndex);

        // 如果当前字符c已经有匹配的string
        if (map.containsKey(c)) {
            String matchedStr = map.get(c);

            // 如果string剩余的部分并非以已匹配的string开头的话，则pattern不match
            if (!str.startsWith(matchedStr, strIndex)) {
                return false;
            }
            return isMatched(pattern, patternIndex + 1, str, strIndex + matchedStr.length(), set, map);
        }
        // 如果当前字符c目前没有匹配的string, 尝试match各种可能的string
        else {
            for (int i = strIndex; i < str.length(); i++) {
                String candidate = str.substring(strIndex, i + 1);

                // 利用HashSet防止不同的字符对应一样的string
                if (set.contains(candidate)) {
                    continue;
                }

                set.add(candidate);
                map.put(c, candidate);

                if (isMatched(pattern, patternIndex + 1, str, i + 1, set, map)) {
                    return true;
                }

                map.remove(c);
                set.remove(candidate);
            }
            return false;
        }
    }
}
```

## 3. Time & Space Complexity

**Backtracking:** 时间复杂度O(n \* C(m, n)),n是str的长度, m为pattern的长度，这个问题相当于将str分成m份，而分的方法是C(n, m),每部分都要O(n)时间验证, 空间复杂度O(m + n + n) => O(m + n), 递归的所需空间最多为n, set的空间最多为n, map的空间最多为n