数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中的单词模式 II
假设我们有一个模式和一个称为 str 的字符串，我们需要检查 str 是否遵循相同的模式。这里的模式匹配意味着完全匹配，即模式中的字母和 str 中的非空子字符串之间存在双射关系。
因此，如果输入模式为“abaa”，str 为“orangegreenorangeorange”，则输出为 true
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 solve()，它将接收 i、j、ptr、s、一个映射 m、一个集合 used 作为参数。
如果 i >= s 的大小 且 j >= ptr 的大小，则：
返回 true
如果 i >= s 的大小 或 j >= ptr 的大小，则：
返回 false
如果 ptr[j] 存在于 m 中，则：
req := m[ptr[j]]
len := req 的大小
如果 len > s 的大小，则：
返回 false
如果 s 从索引 (i 到 len-1) 的子字符串与 req 相同且 solve(i + len, j + 1, ptr, s, m, used) 为真，则：
返回 true
返回 false
否则
x := ptr[j]
对于 k 从 i 初始化，当 k < s 的大小时，更新 (k 增加 1)，执行：
temp := s 从索引 (i 到 k - i) 的子字符串
如果 temp 存在于 used 中，则：
忽略以下部分，跳到下一次迭代
m[x] := temp
将 temp 插入 used
如果 solve(k + 1, j + 1, ptr, s, m, used) 为真，则：
返回 true
从 m 中删除 x
从 used 中删除 temp
返回 false
在主方法中执行以下操作：
定义一个映射 m
定义一个集合 used
返回 solve(0, 0, ptr, s, m, used)
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(int i, int j, string ptr, string s, map <char, string>& m, set<string>& used){
if (i >= s.size() && j >= ptr.size()) {
return true;
}
if (i >= s.size() || j >= ptr.size())
return false;
if (m.count(ptr[j])) {
string req = m[ptr[j]];
int len = req.size();
if (len > s.size() - i)
return false;
if ((s.substr(i, len) == req) && solve(i + len, j + 1, ptr, s, m, used))
return true;
return false;
}
else {
char x = ptr[j];
for (int k = i; k < s.size(); k++) {
string temp = s.substr(i, k - i + 1);
;
if (used.count(temp))
continue;
m[x] = temp;
used.insert(temp);
if (solve(k + 1, j + 1, ptr, s, m, used))
return true;
m.erase(x);
used.erase(temp);
}
}
return false;
}
bool wordPatternMatch(string ptr, string s) {
map<char, string> m;
set<string> used;
return solve(0, 0, ptr, s, m, used);
}
};
main(){
Solution ob;
cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
}输入
"abaa" "orangegreenorangeorange"
输出
1
199 次浏览
