# My java solution, with both recursive and DP versions

• ``````public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// return recursive(s1.toCharArray(),s2.toCharArray(),s3.toCharArray(),  0, 0, 0);
char ss1[] = s1.toCharArray();
char ss2[] = s2.toCharArray();
char ss3[] = s3.toCharArray();

boolean ok[][][] = new boolean[ss1.length+1][ss2.length+1][ss3.length+1];

for(int i=0;i<=ss1.length;i++)
for(int j=0;j<=ss2.length;j++)
ok[i][j][0] = false;

for(int i=0;i<=ss3.length;i++) {
ok[0][0][i] = false;
}

ok[0][0][0] = true;

for(int k=1;k<=ss3.length;k++) {
for(int i=0;i<=ss1.length;i++) {
for(int j=0;j<=ss2.length;j++) {
ok[i][j][k] =  (i>0 && ss3[k-1] == ss1[i-1]) && ok[i-1][j][k-1]  ||
( j>0 && ss3[k-1] == ss2[j-1]) && ok[i][j-1][k-1] ;
}
}
}

return ok[ss1.length][ss2.length][ss3.length];
}

boolean recursive(char s1[], char s2[], char s3[], int p1, int p2, int p3) {
boolean result = false;
if ( p1 == s1.length && p2 == s2.length && p3 == s3.length ) return true;
// if any 2  are full but the other is not, can't match.
if ( (p1 == s1.length &&  p2 == s2.length  ||
p3 == s3.length  )) return false;

return
p3<s3.length && p1<s1.length && s3[p3] == s1[p1] &&  recursive(s1,s2,s3, p1+1, p2, p3+1)
||
p3<s3.length && p2<s2.length && s3[p3] == s2[p2] &&  recursive(s1,s2,s3, p1, p2+1, p3+1);
}
``````

}

• This post is deleted!

• to someone's earlier comment: yes the recursive version logic proves correct by all test cases , but fails due to time limit exception in one really long case.

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