Minimum ASCII Delete Sum for Two Strings

Medium
Watch on YouTube ↗

Solution

/*************Recursive with Memoization************** */
class Solution {
    Integer dp[][];
    public int minimumDeleteSum(String s1, String s2) {
        dp = new Integer[s1.length()][s2.length()];
        return helper(s1, s2, 0, 0);
    }

    int helper(String s1, String s2, int i, int j) {
        // base case
        if(i>=s1.length() || j>=s2.length()) {
            return remSum(s1, i) + remSum(s2, j);
        }
        if(dp[i][j]!=null) {
            return dp[i][j];
        }
        int ans = 0;
        if(s1.charAt(i)==s2.charAt(j)) {
            ans = helper(s1, s2, i+1, j+1);
        }
        else {
            ans = Math.min(s1.charAt(i) + helper(s1, s2, i+1, j), 
                            s2.charAt(j) + helper(s1, s2, i, j+1));
        }
        return dp[i][j] = ans;
    }

    int remSum(String str, int ind) {
        int sum = 0;
        for(int i=ind; i<str.length(); i++) {
            sum += str.charAt(i);
        }
        return sum;
    }
}


/*************Iterative DP Solution************** */

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int dp[][] = new int[m+1][n+1];

        // s1 exhausted
        for(int j=n-1; j>=0; j--) {
            dp[m][j] = dp[m][j+1] + s2.charAt(j);
        }

        // s2 exhausted
        for(int i=m-1; i>=0; i--) {
            dp[i][n] = dp[i+1][n] + s1.charAt(i);
        }

        for(int i=m-1; i>=0; i--) {
            for(int j=n-1; j>=0; j--) {
                if(s1.charAt(i)==s2.charAt(j)) {
                    dp[i][j] = dp[i+1][j+1];
                } else {
                    dp[i][j] = Math.min(s1.charAt(i) + dp[i+1][j],
                    s2.charAt(j) + dp[i][j+1]);
                }
            }
        }

        return dp[0][0];


    }
}