Concise DP solution


  • 10

    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()];   
        }
    }
    ``

  • 7
    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!


  • 0
    D

    another Java solution

    public int minimumDeleteSum(String s1, String s2) {
            int m = s1.length(), n = s2.length();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                dp[i][0] = s1.charAt(i - 1) + dp[i - 1][0]; 
            }
            for (int j = 1; j <= n; j++) {
                dp[0][j] = s2.charAt(j - 1) + dp[0][j - 1];
            }
            
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    // if i - 1 and j - 1 are the same, use the previous result 
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    // else compare the sums of previous results and current 
                    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];
            
            
        }

  • 0

    Similarly edit distance algorithm bottom-up, 13 line

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

    Although I would recommend converting toCharArray first.


Log in to reply
 

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