C ++中的单词模式II
假设我们有一个模式和一个叫做str的字符串，我们必须检查str是否遵循相同的模式。这里的模式跟随表示完全匹配，因此模式中的字母与str中的非空子字符串之间存在双射。
因此，如果输入像模式是“abaa”，str是“orangegreenorangeorange”，那么输出将为true
为了解决这个问题，我们将遵循以下步骤-
定义一个函数solve()，它将使用i，j，ptr，s，一个映射m，一个称为used的集合，
如果i>=s的大小而j>=ptr的大小，则-
返回真
如果i>=s的大小或j>=ptr的大小，则-
返回假
如果ptr[j]以m为单位，则-
返回真
返回假
要求：=m[ptr[j]]
len：=需求大小
如果len>s的大小，则-
如果从索引（i到len-1）的s的子字符串与req和solve（i+len，j+1，ptr，s，m，used）相同，则-
返回假
除此以外
temp：=s从索引（i到k-i）的子字符串
如果使用temp，则-
m[x]：=温度
将temp插入二手
如果solve（k+1，j+1，ptr，s，m，使用），则-
从m删除x
从使用中删除温度
忽略以下部分，跳至下一个迭代
返回真
x：=ptr[j]
对于初始化k：=i，当k<s的大小时，更新（将k增加1），-
返回假
从主要方法中执行以下操作-
定义一张映射
定义一套
返回solve（0，0，ptr，s，m，使用）
例
让我们看下面的实现以更好地理解-
#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