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