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[0][0] = true; for (int i = 1; i <= s1.length(); i++) { isInterleave[i][0] = isInterleave[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1); } for (int j = 1; j <= s2.length(); j++) { isInterleave[0][j] = isInterleave[0][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()]; }