Java top-down DP AC Solution


  • 2
    S
    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length()+s2.length()!=s3.length()) return false;
            Boolean[][][] mem = new Boolean[s1.length()+1][s2.length()+1][s3.length()+1];
            return isInterleaveR(s1,s2,s3,0,0,0,mem);
        }
        
        
        public boolean isInterleaveR(String s1, String s2, String s3, int n1, int n2, int n3,Boolean[][][] mem) {
            
            if(mem[n1][n2][n3]!=null) {
                return mem[n1][n2][n3];
            }
            
            
            if(n3==s3.length()&&n2==s2.length()&&n1==s1.length()){
                return true;
            }
            
            char c3 = s3.charAt(n3);
            char c2 = n2<s2.length()?s2.charAt(n2):0;
            char c1 = n1<s1.length()?s1.charAt(n1):0;
            boolean r = false;
     
            if(c3==c1&&c3!=c2){
                r = isInterleaveR(s1,s2,s3,n1+1,n2,n3+1,mem);
            }
            if(c3!=c1&&c3==c2){
                r = isInterleaveR(s1,s2,s3,n1,n2+1,n3+1,mem);
            }
            if(c3==c1&&c3==c2){
                r = isInterleaveR(s1,s2,s3,n1+1,n2,n3+1,mem) || isInterleaveR(s1,s2,s3,n1,n2+1,n3+1,mem);
            }
            mem[n1][n2][n3]=r;
            return r;
        }
    }
    

Log in to reply
 

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