1m Java DP Solution


  • 0
    M
    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;
            }
        }
            
        }
        
    }
    

Log in to reply
 

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