C++の単語パターンII

したがって、入力が「abaa」、strが「orangegreenorangeorange」のような場合、出力はtrueになります

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これには、i、j、ptr、s、マップm、usedと呼ばれる1つのセットが必要です。

• 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

    • temp：=インデックスからのsの部分文字列（iからk --i）

    • tempが使用されている場合、-

      • 次の部分を無視し、次の反復にスキップします

    • m [x]：=temp

    • 使用済みに温度を挿入

    • Solve（k + 1、j + 1、ptr、s、m、used）の場合、-

      • trueを返す

    • mからxを削除

    • 使用済みから一時を削除

• falseを返す

• メインの方法から、次のようにします-

• 1つのマップを定義するm

• 使用するセットを1つ定義する

• 戻り値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