C++ solution using subsequence


#1

int subs(string A,string B){
int a=A.length(),b=B.length();
vector<vector > dp(b+1,vector (a+1,0));
for(int i=0;i<b;i++)
for(int j=0;j<a;j++)
if(B[i]==A[j])dp[i+1][j+1]=dp[i][j]+1;
else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
return dp[b][a];
}
int Solution::isInterleave(string A, string B, string C) {
if(subs(A,C)==A.length() and subs(B,C)==B.length() and C.length()<=A.length()+B.length())return 1;
return 0;
}