2 solutions, easy-to-understand


  • 0
    S

    public class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {
        int len1;
        int len2;
        int len3;
        if(s1==null) len1 = 0;
            else len1 = s1.length();
        if(s2==null) len2 = 0;
            else len2 = s2.length();
        if(s3==null) len3 = 0;
            else len3 = s3.length();
        char[]v1 = s1.toCharArray();
        char[]v2 = s2.toCharArray();
        char[]v3 = s3.toCharArray();
        if((len1+len2)!=len3) return false;
        boolean[][] dp = new boolean[len1+1][len2+1];
        for(boolean[] row:dp) Arrays.fill(row,false);
        dp[0][0] = true;
        for(int i=1; i<=len1; i++){
            if(v1[i-1]==v3[i-1]&&dp[i-1][0]) dp[i][0] = true;
        }
        for(int j=1; j<=len2; j++){
            if(v2[j-1]==v3[j-1]&&dp[0][j-1]) dp[0][j] = true;
        }
        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                dp[i][j] = ((dp[i][j-1]&&v2[j-1]==v3[i+j-1]) || dp[i-1][j]&&v1[i-1]==v3[i+j-1]);
            }
        }
        return dp[len1][len2];
       /* //improve!~~
        int len1;
        int len2;
        int len3;
        if(s1==null) len1 = 0;
            else len1 = s1.length();
        if(s2==null) len2 = 0;
            else len2 = s2.length();
        if(s3==null) len3 = 0;
            else len3 = s3.length();
            if(len1+len2!=len3) return false;
            char[] v1 = s1.toCharArray();
            char[] v2 = s2.toCharArray();
            char[] v3 = s3.toCharArray();
            boolean[] dp = new boolean[len2+1];
            Arrays.fill(dp,false);
            dp[0] = true;
            for(int j=1; j<=len2; j++){
                if(dp[j-1] && v2[j-1]==v3[j-1]) dp[j] = true;
            }
            for(int i=1; i<=len1; i++){
                dp[0] = dp[0]&&v1[i-1]==v3[i-1];                 for(int j=1; j<=len2; j++){
                    dp[j] = (dp[j-1]&&v2[j-1]==v3[i+j-1] || dp[j]&&v1[i-1]==v3[i+j-1]);
                }
            }
            return dp[len2];*/
    }
    

    }


Log in to reply
 

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