# [LeetCode] 291. Word Pattern II 词语模式 II

2021年09月15日 阅读数：1

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

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

Examples:app

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

290. Word Pattern 的拓展，区别是这里的单词字符串没有空格了，不能按空格把单词直接拆分出来。post

Python:code

```# Time:  O(n * C(n - 1, c - 1)), n is length of str, c is unique count of pattern,
#                                there are H(n - c, c - 1) = C(n - 1, c - 1) possible splits of string,
#                                and each one costs O(n) to check if it matches the word pattern.
# Space: O(n + c)

class Solution(object):
def wordPatternMatch(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
w2p, p2w = {}, {}
return self.match(pattern, str, 0, 0, w2p, p2w)

def match(self, pattern, str, i, j, w2p, p2w):
is_match = False
if i == len(pattern) and j == len(str):
is_match = True
elif i < len(pattern) and j < len(str):
p = pattern[i]
if p in p2w:
w = p2w[p]
if w == str[j:j+len(w)]:  # Match pattern.
is_match = self.match(pattern, str, i + 1, j + len(w), w2p, p2w)
# Else return false.
else:
for k in xrange(j, len(str)):  # Try any possible word
w = str[j:k+1]
if w not in w2p:
# Build mapping. Space: O(n + c)
w2p[w], p2w[p] = p, w;
is_match = self.match(pattern, str, i + 1, k + 1, w2p, p2w)
w2p.pop(w), p2w.pop(p);
if is_match:
break
return is_match　　```

C++：htm

```class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> m;
return helper(pattern, 0, str, 0, m);
}
bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m) {
if (p == pattern.size() && r == str.size()) return true;
if (p == pattern.size() || r == str.size()) return false;
char c = pattern[p];
for (int i = r; i < str.size(); ++i) {
string t = str.substr(r, i - r + 1);
if (m.count(c) && m[c] == t) {
if (helper(pattern, p + 1, str, i + 1, m)) return true;
} else if (!m.count(c)) {
bool b = false;
for (auto it : m) {
if (it.second == t) b = true;
}
if (!b) {
m[c] = t;
if (helper(pattern, p + 1, str, i + 1, m)) return true;
m.erase(c);
}
}
}
return false;
}
};　　```

C++:blog

```class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> m;
set<string> s;
return helper(pattern, 0, str, 0, m, s);
}
bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m, set<string> &s) {
if (p == pattern.size() && r == str.size()) return true;
if (p == pattern.size() || r == str.size()) return false;
char c = pattern[p];
for (int i = r; i < str.size(); ++i) {
string t = str.substr(r, i - r + 1);
if (m.count(c) && m[c] == t) {
if (helper(pattern, p + 1, str, i + 1, m, s)) return true;
} else if (!m.count(c)) {
if (s.count(t)) continue;
m[c] = t;
s.insert(t);
if (helper(pattern, p + 1, str, i + 1, m, s)) return true;
m.erase(c);
s.erase(t);
}
}
return false;
}
};
```