C ++中的单词模式II

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个模式和一个叫做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

      以上是 C ++中的单词模式II 的全部内容， 来源链接： utcz.com/z/317133.html

      回到顶部