# [Java] concise O(n) space solution with minor optimization converted from pure DFS

1. A minor optimization can be exchanging s1 with s2 when s1.length is smaller than s2.length. In this way, we can save some space when initializing a 1D dp array.

2. I was stuck in TLE by my DFS version solution, finally, I reached this dp version by converting my original one. Hopefully, it can help. :)

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;
}
if (len1 < len2) {
// to save space for dp array
return isInterleave(s2, s1, s3);
}
boolean[] dp = new boolean[len2 + 1];
for (int i = len1; i >= 0; i--) {
for (int j = len2; j >= 0; j--) {
int k = i + j;
if (k == len3) {
dp[j] = true;
} else {
dp[j] = (i < len1 && s1.charAt(i) == s3.charAt(k) && dp[j])
// able to match s3[k] using s1[i] ?
||
(j < len2 && s2.charAt(j) == s3.charAt(k) && dp[j + 1]);
// able to match s3[k] using s2[j] ?
}
}
}

``````return dp[0];
``````

}

Originally TLE backtracking version:

``````public class SolutionDFS {
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;
}
// backtracking
return isInterleave(s1, s2, s3, 0, 0);
}

private boolean isInterleave(String s1, String s2, String s3,
int i, int j) {
// base base
int k = i + j;
if (k == s3.length()) {
return true;
}

// recursive case: next character may be from either s1 or s2
return ((i < s1.length() && s1.charAt(i) == s3.charAt(k) &&
isInterleave(s1, s2, s3, i + 1, j)) ||
(j < s2.length() && s2.charAt(j) == s3.charAt(k) &&
isInterleave(s1, s2, s3, i, j + 1)));
}

}``````

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