# interleaving string

## interleaving string

### Dynamic progaming

This problem is a dynamic programing problem.Assuming that `dp[i][j]`

stands for whether `s1.substr(0,i)`

and`s2.substr(0,j)`

can form `s3.substr(0,i+j)`

. And `dp[i][j]`

can be transformed from `dp[i-1][j]`

or `dp[i][j-1]`

The transfer equation is `dp[i][j] = ( dp[i-1][j] && s1[i-1] == s3[i+j-1] ) || ( dp[i][j-1] && s2[j-1] == s3[i+j-1] )`

.

```
1 class Solution {
2 public:
3 bool isInterleave(string s1, string s2, string s3) {
4 int l1 = s1.length();
5 int l2 = s2.length();
6 if ( l1+l2 != s3.length() ) {
7 return false;
8 }
9 if ( 0 == l1 ){
10 return s2 == s3;
11 }
12 if ( 0 == l2 ) {
13 return s1 == s3;
14 }
15 bool dp[l1+1][l2+1];
16 memset(dp,0,sizeof(dp));
17 dp[0][0] = 1;
18 for ( int i = 1; i <= l1; i++ ){
19 dp[i][0] = dp[i-1][0]&&(s1[i-1] == s3[i-1]);
20 }
21 for ( int j = 1; j <= l2; j++ ) {
22 dp[0][j] = dp[0][j-1]&&(s2[j-1] == s3[j-1]);
23 }
24 for ( int i = 1; i <= l1; i++ ) {
25 for ( int j = 1; j <= l2; j++ ) {
26 dp[i][j] = ( ( dp[i-1][j] && ( s1[i-1] == s3[i+j-1] ) ) || ( dp[i][j-1] && ( s2[j-1] == s3[i+j-1] ) ) );
27 }
28 }
29 return dp[l1][l2];
30 }
31 };
```