LeetCode 712: Minimum ASCII Delete Sum for Two Strings Solution

Master LeetCode problem 712 (Minimum ASCII Delete Sum for Two Strings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

712. Minimum ASCII Delete Sum for Two Strings

Medium

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can create a 2D array dp where dp[i][j] represents the minimum ASCII sum of deleted characters to make s1[0...i-1] and s2[0...j-1] equal.

The recursive formula is as follows:

If s1[i-1] == s2[j-1], then dp[i][j] = dp[i-1][j-1].
Otherwise, we have two options:
1. Delete s1[i-1]: dp[i][j] = dp[i-1][j] + s1[i-1].
2. Delete s2[j-1]: dp[i][j] = dp[i][j-1] + s2[j-1]. We choose the minimum of the two options.

We initialize the base cases where if one string is empty, the cost is the sum of ASCII values of the characters in the non-empty string.

The final answer will be dp[s1.length()][s2.length()].

Time Complexity: O(mn) where m and n are the lengths of s1 and s2 respectively. Space Complexity: O(mn) for the 2D array dp.

Solution Code

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 712 (Minimum ASCII Delete Sum for Two Strings)?

This page provides optimized solutions for LeetCode problem 712 (Minimum ASCII Delete Sum for Two Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 712 (Minimum ASCII Delete Sum for Two Strings)?

The time complexity for LeetCode 712 (Minimum ASCII Delete Sum for Two Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 712 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 712 in Java, C++, or Python.

Back to LeetCode Solutions