---
comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/solution/0200-0299/0291.Word%20Pattern%20II/README.md
tags:
- 哈希表
- 字符串
- 回溯
---
# [291. 单词规律 II 🔒](https://leetcode.cn/problems/word-pattern-ii)
[English Version](/solution/0200-0299/0291.Word%20Pattern%20II/README_EN.md)
## 题目描述
给你一种规律 pattern 和一个字符串 s，请你判断 s 是否和 pattern 的规律相匹配。
如果存在单个字符到 非空 字符串的 双射映射 ，那么字符串 s 匹配 pattern ，即：如果 pattern 中的每个字符都被它映射到的字符串替换，那么最终的字符串则为 s 。双射 意味着映射双方一一对应，不会存在两个字符映射到同一个字符串，也不会存在一个字符分别映射到两个不同的字符串。
示例 1：
输入：pattern = "abab", s = "redblueredblue"
输出：true
解释：一种可能的映射如下：
'a' -> "red"
'b' -> "blue"
示例 2：
输入：pattern = "aaaa", s = "asdasdasdasd"
输出：true
解释：一种可能的映射如下：
'a' -> "asd"
示例 3：
输入：pattern = "aabb", s = "xyzabcxzyabc"
输出：false
提示：
1 <= pattern.length, s.length <= 20pattern 和 s 由小写英文字母组成
## 解法
### 方法一
#### Python3
```python
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
def dfs(i, j):
if i == m and j == n:
return True
if i == m or j == n or n - j < m - i:
return False
for k in range(j, n):
t = s[j : k + 1]
if d.get(pattern[i]) == t:
if dfs(i + 1, k + 1):
return True
if pattern[i] not in d and t not in vis:
d[pattern[i]] = t
vis.add(t)
if dfs(i + 1, k + 1):
return True
d.pop(pattern[i])
vis.remove(t)
return False
m, n = len(pattern), len(s)
d = {}
vis = set()
return dfs(0, 0)
```
#### Java
```java
class Solution {
private Set vis;
private Map d;
private String p;
private String s;
private int m;
private int n;
public boolean wordPatternMatch(String pattern, String s) {
vis = new HashSet<>();
d = new HashMap<>();
this.p = pattern;
this.s = s;
m = p.length();
n = s.length();
return dfs(0, 0);
}
private boolean dfs(int i, int j) {
if (i == m && j == n) {
return true;
}
if (i == m || j == n || m - i > n - j) {
return false;
}
char c = p.charAt(i);
for (int k = j + 1; k <= n; ++k) {
String t = s.substring(j, k);
if (d.getOrDefault(c, "").equals(t)) {
if (dfs(i + 1, k)) {
return true;
}
}
if (!d.containsKey(c) && !vis.contains(t)) {
d.put(c, t);
vis.add(t);
if (dfs(i + 1, k)) {
return true;
}
vis.remove(t);
d.remove(c);
}
}
return false;
}
}
```
#### C++
```cpp
class Solution {
public:
bool wordPatternMatch(string pattern, string s) {
unordered_set vis;
unordered_map d;
return dfs(0, 0, pattern, s, vis, d);
}
bool dfs(int i, int j, string& p, string& s, unordered_set& vis, unordered_map& d) {
int m = p.size(), n = s.size();
if (i == m && j == n) return true;
if (i == m || j == n || m - i > n - j) return false;
char c = p[i];
for (int k = j + 1; k <= n; ++k) {
string t = s.substr(j, k - j);
if (d.count(c) && d[c] == t) {
if (dfs(i + 1, k, p, s, vis, d)) return true;
}
if (!d.count(c) && !vis.count(t)) {
d[c] = t;
vis.insert(t);
if (dfs(i + 1, k, p, s, vis, d)) return true;
vis.erase(t);
d.erase(c);
}
}
return false;
}
};
```
#### Go
```go
func wordPatternMatch(pattern string, s string) bool {
m, n := len(pattern), len(s)
vis := map[string]bool{}
d := map[byte]string{}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i == m && j == n {
return true
}
if i == m || j == n || m-i > n-j {
return false
}
c := pattern[i]
for k := j + 1; k <= n; k++ {
t := s[j:k]
if v, ok := d[c]; ok && v == t {
if dfs(i+1, k) {
return true
}
}
if _, ok := d[c]; !ok && !vis[t] {
d[c] = t
vis[t] = true
if dfs(i+1, k) {
return true
}
delete(d, c)
vis[t] = false
}
}
return false
}
return dfs(0, 0)
}
```