Sponsored
Sponsored
This approach involves using a 2D table to compute the minimum ASCII delete sum to make the two strings equal. The table is filled using a bottom-up dynamic programming method, considering the cost of deleting characters from either string.
For each index pair (i, j), we decide whether to delete a character from either s1 or s2 or take the sum from previously computed states to minimize the ASCII sum deletion cost.
Time Complexity: O(m * n), where m and n are the lengths of s1 and s2. This is because we need to fill the entire DP table.
Space Complexity: O(m * n), due to storage in a 2D table.
1#include<vector>
2#include<string>
3using namespace std;
4
5class Solution {
6public:
7 int minimumDeleteSum(string s1, string s2) {
8 int m = s1.length(), n = s2.length();
9 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
10
11 for (int i = m - 1; i >= 0; i--)
12 dp[i][n] = dp[i + 1][n] + s1[i];
13
14 for (int j = n - 1; j >= 0; j--)
15 dp[m][j] = dp[m][j + 1] + s2[j];
16
17 for (int i = m - 1; i >= 0; i--) {
18 for (int j = n - 1; j >= 0; j--) {
19 if (s1[i] == s2[j])
20 dp[i][j] = dp[i + 1][j + 1];
21 else
22 dp[i][j] = min(dp[i + 1][j] + s1[i], dp[i][j + 1] + s2[j]);
23 }
24 }
25
26 return dp[0][0];
27 }
28};
29The C++ solution follows the same DP strategy, utilizing a vector for the 2D table. The structure and logic are parallel to the Java and Python solutions.
This approach uses a recursive function with memoization to solve the problem. The recursive function computes the minimum ASCII sum by exploring all possible deletions and storing intermediate results to avoid redundant calculations. This can be a more intuitive approach for those familiar with recursion at the expense of higher time complexity when not optimized with memoization.
Time Complexity: O(m * n) due to memoization reducing the duplicate calculations.
Space Complexity: O(m * n), with space used for the recursion stack and memoization storage.
1public class Solution {
2 private Dictionary<string, int> memo = new Dictionary<string, int>();
3
public int MinimumDeleteSum(string s1, string s2) {
return MinimumDeleteSumHelper(s1, 0, s2, 0);
}
private int MinimumDeleteSumHelper(string s1, int i, string s2, int j) {
if (i == s1.Length) {
int sum = 0;
while (j < s2.Length) {
sum += s2[j++];
}
return sum;
}
if (j == s2.Length) {
int sum = 0;
while (i < s1.Length) {
sum += s1[i++];
}
return sum;
}
string key = i + "," + j;
if (memo.ContainsKey(key)) {
return memo[key];
}
if (s1[i] == s2[j]) {
memo[key] = MinimumDeleteSumHelper(s1, i + 1, s2, j + 1);
} else {
memo[key] = Math.Min(
s1[i] + MinimumDeleteSumHelper(s1, i + 1, s2, j),
s2[j] + MinimumDeleteSumHelper(s1, i, s2, j + 1)
);
}
return memo[key];
}
}
In this solution, we use a memoization dictionary to save results of previous calculations to avoid recomputation. The recursive helper function attempts deletions from s1 or s2 whenever theres is no character match, storing and reusing the computed results to find the minimum ASCII delete sum.