# 1m Java DP Solution

• ``````public class Solution {
int[][] memo;
public boolean isInterleave(String s1, String s2, String s3) {

if(s1.length() + s2.length() != s3.length()){
return false;
}
memo=new int[s1.length()+1][s2.length()+1];
return checkInterLeave(s1,s2,s3,0,0,0);

}
public boolean checkInterLeave(String s1,String s2,String s3,int i1,int i2,int i3){{
if(i1==s1.length() && i2==s2.length() && i3==s3.length()){
return true;
}
if(i3>=s3.length()){
return false;
}
if(i1<s1.length() && i2<s2.length() && memo[i1][i2]==1){
return true;
}else if(i1<s1.length() && i2<s2.length() && memo[i1][i2]==-1){
return false;
}
if(i1<s1.length() && i2<s2.length() && s1.charAt(i1)==s3.charAt(i3) && s2.charAt(i2)==s3.charAt(i3) ){
boolean res = checkInterLeave(s1,s2,s3,i1+1,i2,i3+1);
memo[i1+1][i2]=res?1:-1;
res = checkInterLeave(s1,s2,s3,i1,i2+1,i3+1);
memo[i1][i2+1]=res?1:-1;
return memo[i1][i2+1]==1 || memo[i1+1][i2]==1;
}else if(i1<s1.length() && s1.charAt(i1)==s3.charAt(i3)){
boolean res = checkInterLeave(s1,s2,s3,i1+1,i2,i3+1);
memo[i1+1][i2]=res?1:-1;
return res;
}else if(i2<s2.length() && s2.charAt(i2)==s3.charAt(i3) ){
boolean res = checkInterLeave(s1,s2,s3,i1,i2+1,i3+1);
memo[i1][i2+1]=res?1:-1;
return res;
}else{
return false;
}
}

}

}
``````

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