Java DP solution


  • 0
    A
    public class Solution {
        byte[][][] b;
        public boolean isInterleave(String s1, String s2, String s3) {
            int l1=s1.length();int l2=s2.length();int l3=s3.length();
            if(l3!=l1+l2) return false;
            if(l1==0 && l2!=0) return s2.equals(s3);
            if(l1!=0 && l2==0) return s1.equals(s3);
            b = new byte[l1+1][l2+1][l3+1];
            return isInterleave(s1,s2,s3,0,0,0);
        }
        
        public void initialize(boolean val, int s1, int s2, int s3){
            b[s1][s2][s3]=val==true?(byte)1:(byte)2;
        }
        
        public boolean isInterleave(String s1, String s2, String s3, int start1, int start2,int start3) {
            int l1=s1.length();int l2=s2.length();int l3=s3.length();
            
            if(start3==l3 && start2==l2 && start1==l1){
                b[start1][start2][start3] = 1;
                return true;
            }
            
            int dp = b[start1][start2][start3]; 
            if(dp!=0){
                if(dp==1) return true; else return false;
            }
            
            if(start3>=l3||!((start1<l1 && s3.charAt(start3)==s1.charAt(start1))||(start2<l2 && s3.charAt(start3)==s2.charAt(start2)))){
                b[start1][start2][start3] = 2;
            }
            else if(start1<l1 && start2<l2 && s3.charAt(start3) == s1.charAt(start1) && s3.charAt(start3) == s2.charAt(start2))
            
                initialize(isInterleave(s1,s2,s3,start1+1,start2,start3+1) 
                || isInterleave(s1,s2,s3,start1,start2+1,start3+1), start1, start2, start3);
                
            else if( start1<l1 && s3.charAt(start3) == s1.charAt(start1))
            
                initialize(isInterleave(s1,s2,s3,start1+1,start2,start3+1), start1, start2, start3);
                
            else if(start2<l2 && s3.charAt(start3) == s2.charAt(start2))
            
                initialize(isInterleave(s1,s2,s3,start1,start2+1,start3+1), start1, start2, start3);
                
            else 
                b[start1][start2][start3] = 2;
            
            if(b[start1][start2][start3] == 1) return true; else return false;
        }
    }

Log in to reply
 

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