**Interleaving String**

Given

*s1*,*s2*,*s3*, find whether*s3*is formed by the interleaving of*s1*and*s2*.
For example,

Given:

Given:

*s1*=`"aabcc"`

,*s2*=`"dbbca"`

,
When

When

*s3*=`"aadbbcbcac"`

, return true.When

*s3*=`"aadbbbaccc"`

, return false.### Analysis (Updated 201309):

First we can consider this as a recursive problem.If s3[i1+i2+1] == s1[i1+1], search(i1+1,i2)

If s3[i1+i2+1] == s2[i2+1], search(i1,i2+1)

until end. However, this can only pass the small test cases, but failed on the large test cases.

So we need to think of the dynamic programming (DP), which usually have much less complexity. In this problem, a 2D DP is more suitable. As usual, the typical way of solving dp is to find the state, and the optimal function. Here, the state can be considered as: A[i][j], which means S3[i+j] can be formed by S1[i] and S2[j] (for simplicity here string starts from 1, in the code we need to deal with that string starts from 0).

So, we have the optimal function:

A[i][j] = (s3[i+j]==s1[i] && match[i-1][j]) || (s3[i+j] ==s2[j] && match[i][j-1])

Given the state and the optimal function, we also need to be careful with the initialization. Details see the code below.

### Code(Updated 201312):

class Solution { public: bool isInterleave(string s1, string s2, string s3) { int n1 = s1.size(); int n2 = s2.size(); vector<vector<bool> > A(n1+1,vector<bool>(n2+1,false)); if (n1+n2!=s3.size()){return false;} if (s1.empty()&&s2.empty()&&s3.empty()){return true;} A[0][0]=true; for (int i=1;i<=n1;i++){ if (s1[i-1]==s3[i-1] && A[i-1][0]){A[i][0]=true;} } for (int i=1;i<=n2;i++){ if (s2[i-1]==s3[i-1] && A[0][i-1]){A[0][i]=true;} } for (int i=1;i<=n1;i++){ for (int j=1;j<=n2;j++){ A[i][j]= (A[i][j-1] && (s2[j-1]==s3[i+j-1])) || (A[i-1][j]&& (s1[i-1]==s3[i+j-1])); } } return A[n1][n2]; } };

This comment has been removed by the author.

ReplyDeleteSeems that there might be a bug with this code. What if n1 (or n2) is 0?

ReplyDeleteS1 = empty string

S2 = abcd

S3 = aaad

the code will return true as long as last character of S2 && S3 matches. I think the real check should be

for (int i=1;i<=n1;i++){

if (s1[i-1]==s3[i-1] && A[i-1][0]) {A[i][0]=true;}

}

for (int i=1;i<=n2;i++){

if (s2[i-1]==s3[i-1] && A[0][i-1] ) {A[0][i]=true;}

}

thanks for your reply!

DeleteYes, I did check the code again, when one string is empty, there will have some problem as you said. The reason is the initialization part.

I have already modified the code.

Thanks !