C ++中的交织字符串
为了解决这个问题，我们将遵循以下步骤-
定义一个称为的方法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：=ansORsolve（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