Concise DP solution


  • 8

    The same idea as edit distance. Straightforward 19 lines.

    class Solution {
        public int minimumDeleteSum(String s1, String s2) {
            int[][] count = new int[s1.length() + 1][s2.length() + 1];
            for(int i = 1; i < count.length; i++){
                count[i][0] = count[i-1][0] + s1.charAt(i-1);
            }
            for(int i = 1; i < count[0].length; i++){
                count[0][i] = count[0][i-1] + s2.charAt(i-1);
            }
            for(int i = 1; i < count.length; i++){
                for(int j = 1; j < count[0].length; j++){
                    int cost = (s1.charAt(i-1) == s2.charAt(j-1))? 0 : s1.charAt(i-1) + s2.charAt(j-1);
                    count[i][j] = Math.min(count[i-1][j] + s1.charAt(i-1), count[i][j-1] + s2.charAt(j-1));
                    count[i][j] = Math.min(count[i][j], count[i-1][j-1] + cost);
                }
            }
            return count[s1.length()][s2.length()];   
        }
    }
    ``

  • 5
    Z

    @DonaldTrump Dear President, I rewrote your solution in C++, even shorter.

       int minimumDeleteSum(string s1, string s2) {
            int m = s1.size(), n = s2.size();
            int dp[m+1][n+1] = {0};
            for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j-1]+s2[j-1];
            for (int i = 1; i <= m; i++) {
                dp[i][0] = dp[i-1][0]+s1[i-1];
                for (int j = 1; j <= n; j++) 
                    dp[i][j] = s1[i-1] == s2[j-1]? dp[i-1][j-1]:min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);
            }
            return dp[m][n];
        }
    

  • 0
    N

    In case you didn't realize, your solution can be optimized by using a 1D array, either dp[string1.length()] or dp[string2.length()]


  • 0
    S

    @zestypanda plz change ur name to Kim Joungeun Lol
    You are genius!


Log in to reply
 

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