# Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = `"aabcc"`, s2 = `"dbbca"`

• When s3 = `"aadbbcbcac"`, return `true`.
• When s3 = `"aadbbbaccc"`, return `false`.

Solution: Dynamic Programming
isInterleave[i][j] = if first i chars of s1 and first j chars of s2 is interleave of first i+j chars of s3
isInterleave[i][j] = isInterleave[i – 1][j] && s1.charAt(i – 1) == s3.charAt(i + j – 1))
|| (isInterleave[i][j – 1] && s2.charAt(j – 1) == s3.charAt(i + j – 1))

```public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null
|| s1.length() + s2.length() != s3.length()) {
return false;
}
//isInterleave[i][j] = if first i chars of s1 and first j chars of s2
//is interleave of first i+j chars of s3
boolean[][] isInterleave = new boolean[s1.length() + 1][s2.length() + 1];
isInterleave = true;
for (int i = 1; i <= s1.length(); i++) {
isInterleave[i] = isInterleave[i - 1] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int j = 1; j <= s2.length(); j++) {
isInterleave[j] = isInterleave[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
isInterleave[i][j] = (isInterleave[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (isInterleave[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return isInterleave[s1.length()][s2.length()];
}```