# [LeetCode 97] Interleaving String

### 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];
}
``````