Pretty Neat DP problem ..

The brute force solution sounds exponential .. given that to exhaust all options for s3 of length N, we need to choose N times whether to pick the character i from s1 or s2.

An interview problem with exponential brute force solution is almost 90+% really a DP one.

Define the state DP[i,j] = True if and only if S1{0-->i} Interleaved with S2{0-->j} will result in S3{0-->i+j}

A closer look may show that DP[i,j] == true if

```
1. DP[i-1,j] = true AND S3[i+j] = s1[i] (thus we picked the new char from s1)
```

OR

```
2. DP[i,j-1] = true AND S3[i+j] = s2[j] (thus we picked the new char from s2)
```

here's the code:

```
public bool IsInterleave(string s1, string s2, string s3) {
if(s3.Length != s1.Length + s2.Length) return false;
bool[,] dp = new bool[s1.Length+1, s2.Length+1];
dp[0,0] = true;
for(int i=1; i <= s1.Length; i++){
dp[i,0] = dp[i-1,0] && s3[i-1] == s1[i-1];
}
for(int i=1; i <= s2.Length; i++){
dp[0,i] = dp[0,i-1] && s3[i-1] == s2[i-1];
}
for(int i=1; i <= s1.Length; i++){
for(int j=1; j <= s2.Length; j++){
dp[i,j] = (dp[i-1,j] && s3[i+j-1] == s1[i-1]) || (dp[i,j-1] && s3[i+j-1] == s2[j-1]);
}
}
return dp[s1.Length, s2.Length];
}
```