Shortest and cleanest solution you possible ever seen


  • 1
    C

    If you don't quite understand what's going on, feel free to send me a message. I will be more than happy to explain the idea behind it.

    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()) return false;
        int l1=s1.length(),l2=s2.length(),i,j;
        boolean [][] dp=new boolean[l1+1][l2+1];
        dp[0][0]=true;
        for(i=1;i<=l2;i++) 
            if(s2.charAt(i-1)==s3.charAt(i-1)) dp[0][i]=true;
            else break;
        for(i=1;i<=l1;i++)
            if(s1.charAt(i-1)==s3.charAt(i-1)) dp[i][0]=true;
            else break;
        for(i=1;i<=l1;i++)
            for(j=1;j<=l2;j++){
                char cur=s3.charAt(i+j-1);
                dp[i][j]=(dp[i][j-1]&&cur==s2.charAt(j-1))||(dp[i-1][j]&&cur==s1.charAt(i-1));
            }
        
        return dp[l1][l2];
    }

Log in to reply
 

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