Is it a simple and easy to understand DP Java solution


  • 0
    W
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if(m + n != s3.length())
            return false;
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if(i + j == 0)
                    continue;
                if(i == 0)
                    dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
                else if(j == 0)
                    dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i-1);
                else {
                    char c = s3.charAt(i+j-1);
                    dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == c) || (dp[i][j-1] && s2.charAt(j-1) == c);
                }
            }
        }
        return dp[m][n];
    }

Log in to reply
 

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