C++での文字列のインターリーブ

3つの文字列s1、s2、s3があるとします。次に、s1とs2をインターリーブしてs3が形成されているかどうかを確認します。したがって、文字列が「aabcc」、s2 =「dbbca」、s3が「aadbbcbcac」の場合、結果はtrueになります。

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

• solve（）と呼ばれる1つのメソッドを定義します。これには、s1、s2、s3、および1つの3d配列dp、次にi、j、k

  が必要です。

• i=0かつj=0かつk=0の場合、trueを返します

• dp [i、j、k]が-1でない場合は、dp [i、j、k]

  を返します。

• ans：=false

• j>0かつk>=0かつs2[j]=s3 [k]の場合、

  • ans：=resolve（s1、s2、s3、dp、i – 1、j、k – 1）

• j>0かつk>=0かつs2[j]=s3 [k]の場合、

  • ans：=ans ORsolve（s1、s2、s3、dp、i、j – 1、k – 1）

• set dp [i、j、k]：=ans

• dp [i、j、k]

  を返します

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

• n：=s1のサイズ、m：=s2のサイズ、o：=s3のサイズ

• s1、s2、s3の前に1つの空白スペースを追加します。

• サイズ（n + 1）x（m + 1）x（o + 1）の配列を1つ作成し、これに-1を入力します

• 戻り値solve（s1、s2、s3、dp、n、m、o）

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool solve(string s1, string s2, string s3, vector < vector < vector <int>>>& dp, int i, int j, int k){
      if(i ==0 && j == 0 && k == 0)return true;
      if(dp[i][j][k] !=-1)return dp[i][j][k];
      bool ans = false;
      if(i > 0 && k >= 0 && s1[i] == s3[k]){
         ans = solve(s1, s2, s3, dp, i - 1, j, k - 1);
      }
      if(j >0 && k >=0 && s2[j] == s3[k]){
         ans |= solve(s1, s2, s3, dp, i, j - 1, k - 1);
      }
      return dp[i][j][k] = ans;
   }
   bool isInterleave(string s1, string s2, string s3) {
      int n = s1.size();
      int m = s2.size();
      int o = s3.size();
      s1 = " " + s1;
      s2 = " " + s2;
      s3 = " " + s3;
      vector < vector < vector <int>>> dp(n + 1, vector < vector <int>>(m + 1, vector <int> (o + 1, -1)));
      return solve(s1, s2, s3, dp, n , m , o );
   }
};
main(){
   Solution ob;
   cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
}

入力

"aabcc", "dbbca", "aadbbcbcac"

出力

1