Minimum Ascii Delete Sum For Two Strings - Leetcode Solution

Problem statement:

Given two strings s1 and s2, return the minimum ASCII delete sum of two non-empty strings 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 the ASCII value of "t" (116) to the sum. At the end, both strings are equal, and we add the ASCII value of "e" from both strings to the sum (101+101=202).

Example 2:

Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: Deleting "d" from "delete" adds the ASCII value of "d" (100) to the sum. Deleting "l" from "leet" adds the ASCII value of "l" (108) to the sum. Deleting "e" from "leet" adds the ASCII value of "e" (101) to the sum. Deleting "t" from "leet" adds the ASCII value of "t" (116) to the sum. At the end, both strings are equal, and we add the ASCII value of "e" from both strings to the sum (101+101=202).

Approach:

This problem is a variation of the longest common subsequence problem. To find the minimum ASCII delete sum, we need to find the common subsequence, and then add all the characters not present in the common subsequence for both strings.

We can use dynamic programming to solve this problem. We will make a 2D array dp, where dp[i][j] will represent the minimum ASCII delete sum needed to make the first i characters of s1 equal to the first j characters of s2.

If s1[i - 1] == s2[j - 1], then we don't need to delete any characters, and dp[i][j] will be equal to dp[i-1][j-1]. Otherwise, we have two options: either delete s1[i - 1] or s2[j - 1], and take the option that requires minimum ASCII delete sum.

The final answer will be dp[m][n], where m and n are the lengths of s1 and s2, respectively.

Code:

Here is the Python code to solve the problem:

def minimumDeleteSum(s1: str, s2: str) -> int: m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m+1): dp[i][0] = dp[i-1][0] + ord(s1[i-1]) for j in range(1, n+1): dp[0][j] = dp[0][j-1] + ord(s2[j-1]) for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])) return dp[m][n]

Time Complexity:

The time complexity of the above code is O(m*n), where m and n are the lengths of s1 and s2, respectively. We are filling a 2D array of size (m+1) x (n+1), and each cell takes O(1) time to fill.

Space Complexity:

The space complexity of the above code is O(m*n), where m and n are the lengths of s1 and s2, respectively. We are using a 2D array of size (m+1) x (n+1).

1