# Java DP solution O(m*n) time, O(n) space!

• ``````public class Solution {
/**
* Dynamic programming
* Dynamic programming has 2 properties: overlapping subproblems and optimal substructure.
* Then for this question, the overlapping subproblem would be matching substring of s1 or s2 with substring of s3.
* Since s3 must match s1 and s2 in a way that the character has the same order, so we can just start comparison from start to end.
* Say, s1.charAt(i) == s3.charAt(i + j); then we only have to deal with the subproblem of s1.substring(i + 1, s1.length()), s2.substring(j, s2.length()) and s3.substring(i + j, s3.length())
* Since we don't have to know exactly how they match but rather only if they have matched for previous characters, a 2-dimensional boolean array would be enough.
* One dimension record the index of s1 and the other record the index of s2.
* matched[i][j] = matched[i][j-1] && current character of s2 and s3 is the same || matched[i-1][j] && current character of s1 and s3 is the same
* Base case would be matched[0][0] = true
* The corner case would be s1.length() + s2.length() != s3.length(), which is obviously false.
* O(m * n) time and space where m and n are length of s1 and s2 respectively
* The space may be further optimized to O(n), see below.
*/

public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s1.length() == 0) {
return s2.equals(s3);
}
if (s2 == null || s2.length() == 0) {
return s1.equals(s3);
}
if (s1.length() + s2.length() != s3.length()) {
return false;
}

boolean[][] matched = new boolean[s1.length() + 1][s2.length() + 1];
char[] ch1 = s1.toCharArray();
char[] ch2 = s2.toCharArray();
char[] ch3 = s3.toCharArray();

for (int i = 0; i <= ch1.length; i++) {
for (int j = 0; j <= ch2.length; j++) {
if (i == 0 && j == 0) {
matched[i][j] = true;
} else if (i == 0) {
matched[i][j] = matched[i][j-1] && ch2[j - 1] == ch3[i + j - 1];
} else if (j == 0) {
matched[i][j] = matched[i - 1][j] && ch1[i - 1] == ch3[i + j - 1];
} else {
matched[i][j] = (matched[i][j - 1] && ch2[j - 1] == ch3[i + j - 1] || matched[i - 1][j] && ch1[i - 1] == ch3[i + j - 1]);
}
}
}

return matched[ch1.length][ch2.length];
}
``````

Since every matched flag is only related to the flag on the right and above it, we can drop every other flags and only retain a 1-dimension array to store these flags.

``````public Solution {
/**
* Further optimized to O(m * n) time and O(n) space where m and n are the length of s1 and s2 respectively
*/
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null) {
return false;
}
if (s1.length() + s2.length() != s3.length()) {
return false;
}

char[] ch1 = s1.toCharArray();
char[] ch2 = s2.toCharArray();
char[] ch3 = s3.toCharArray();
boolean[] matched = new boolean[ch2.length + 1];
for (int i = 0; i <= ch1.length; i++) {
for (int j = 0; j <= ch2.length; j++) {
if (i == 0 && j == 0) {
matched[j] = true;
} else if (i == 0) {
matched[j] = matched[j - 1] && ch2[j - 1] == ch3[i + j -1];
} else if (j == 0) {
matched[j] = matched[j] && ch1[i - 1] == ch3[i + j - 1];
} else {
matched[j] = matched[j - 1] && ch2[j - 1] == ch3[i + j - 1] || matched[j] && ch1[i - 1] == ch3[i + j - 1];
}
}
}

return matched[ch2.length];
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.