### Question

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

For example,

Given:

*s1* = `"aabcc"`

,

*s2* = `"dbbca"`

,

When *s3* = `"aadbbcbcac"`

, return true.

When *s3* = `"aadbbbaccc"`

, return false.

### Stats

Frequency | 2 |

Difficulty | 5 |

Adjusted Difficulty | 3 |

Time to use | -------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This is a DP question**.

At first look it might look like very easily solved by DFS. It it, but TLE exception.

So, I learnt the idea from this blog. It’s easy to realize this is a **very standard DP question**.

### Solution

Declare a 2-D array for DP, and dp(i)(j) denotes whether it’s possible to construct s3 (of length i+j) by using s1 (of length i) and s2 (of length j).

Only thing needs to mention is the size of dp is (m+1)*(n+1), because i = [0, m] and j = [0, n].

### Code

**DP solution**

```
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if (len1 + len2 != len3) return false;
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for (int i = 1; i <= len2; i ++)
dp[0][i] = dp[0][i - 1] & s2.charAt(i-1) == s3.charAt(i-1);
for (int i = 1; i <= len1; i ++)
dp[i][0] = dp[i-1][0] & s1.charAt(i-1) == s3.charAt(i-1);
for (int i = 1; i <= len1; i ++) {
for (int j = 1; j <= len2; j ++) {
if (s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j])
dp[i][j] = true;
if (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1])
dp[i][j] = true;
}
}
return dp[len1][len2];
}
```