Clean Java DP Solution


  • 0
    S

    Standard 2D dp problem;

    dp[i][j] stands for the minimum cost of s1.substring(0, i) and s2.substring(0, j) 's delete sum.

    class Solution {
        public int minimumDeleteSum(String s1, String s2) {
            if(s1 == null || s2 == null) return 0;
            int m = s1.length(), n = s2.length();
            int[][] dp = new int[m+1][n+1];
            for(int i = 1; i < m+1; i++) {
                dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
            }
            for(int j = 1; j < n+1; j++) {
                dp[0][j] = dp[0][j-1] + s2.charAt(j-1);
            }
            for(int i = 1; i < m+1; i++) {
                for(int j = 1; j < n+1; j++) {
                    if(s1.charAt(i-1) == s2.charAt(j-1)) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    else {
                        dp[i][j] = Math.min(dp[i-1][j] + s1.charAt(i-1), dp[i][j-1] + s2.charAt(j-1));
                    }
                }
            }
            return dp[m][n];
        }
    }
    

Log in to reply
 

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