C ++中的交织字符串

假设我们有三个字符串s1，s2和s3。然后检查是否通过交错s1和s2形成s3。因此，如果字符串是“ aabcc”，s2 =“ dbbca”，而s3是“ aadbbcbcac”，则结果为true。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为的方法solve()，它将采用s1，s2，s3和一个3d数组dp，然后是i，j，k

• 如果i = 0和j = 0且k = 0，则返回true

• 如果dp [i，j，k]不为-1，则返回dp [i，j，k]

• 回答：=假

• 如果j> 0且k> = 0且s2 [j] = s3 [k]，则

• ans：= solve（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）

• 设置dp [i，j，k]：= ans

• 返回dp [i，j，k]

• 从主要方法中，执行以下操作-

• n：= s1的大小，m：= s2的大小，o：= s3的大小

• 在s1，s2，s3之前添加一个空格。

• 制作一个大小为（n + 1）x（m + 1）x（o + 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