712. Minimum ASCII Delete Sum for Two Strings LeetCode Solution

In this guide, you will get 712. Minimum ASCII Delete Sum for Two Strings LeetCode Solution with the best time and space complexity. The solution to Minimum ASCII Delete Sum for Two Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum ASCII Delete Sum for Two Strings solution in C++
4. Minimum ASCII Delete Sum for Two Strings solution in Java
5. Minimum ASCII Delete Sum for Two Strings solution in Python
6. Additional Resources

Problem Statement of Minimum ASCII Delete Sum for Two Strings

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = “sea”, s2 = “eat”
Output: 231
Explanation: Deleting “s” from “sea” adds the ASCII value of “s” (115) to the sum.
Deleting “t” from “eat” adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = “delete”, s2 = “leet”
Output: 403
Explanation: Deleting “dee” from “delete” to turn the string into “let”,
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting “e” from “leet” adds 101[e] to the sum.
At the end, both strings are equal to “let”, and the answer is 100+101+101+101 = 403.
If instead we turned both strings into “lee” or “eet”, we would get answers of 433 or 417, which are higher.

Constraints:

1 <= s1.length, s2.length <= 1000
s1 and s2 consist of lowercase English letters.

Complexity Analysis

• Time Complexity: O(mn)
• Space Complexity: O(mn)

712. Minimum ASCII Delete Sum for Two Strings LeetCode Solution in C++

class Solution {
 public:
  int minimumDeleteSum(string s1, string s2) {
    const int m = s1.length();
    const int n = s2.length();
    // dp[i][j] := the minimum cost to make s1[0..i) and s2[0..j) equal
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // Delete s1[i - 1].
    for (int i = 1; i <= m; ++i)
      dp[i][0] = dp[i - 1][0] + s1[i - 1];

    // Delete s2[j - 1].
    for (int j = 1; j <= n; ++j)
      dp[0][j] = dp[0][j - 1] + s2[j - 1];

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (s1[i - 1] == s2[j - 1])
          dp[i][j] = dp[i - 1][j - 1];
        else
          dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);

    return dp[m][n];
  }
};
/* code provided by PROGIEZ */

712. Minimum ASCII Delete Sum for Two Strings LeetCode Solution in Java

class Solution {
  public int minimumDeleteSum(String s1, String s2) {
    final int m = s1.length();
    final int n = s2.length();
    // dp[i][j] := the minimum cost to make s1[0..i) and s2[0..j) equal
    int[][] dp = new int[m + 1][n + 1];

    // Delete s1[i - 1].
    for (int i = 1; i <= m; ++i)
      dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);

    // Delete s2[j - 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];
  }
}
// code provided by PROGIEZ

712. Minimum ASCII Delete Sum for Two Strings LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.