Dynamic Programming: Minimum ASCII Delete Sum for Two Strings
As the title says, this will be a DP solution. Here is the Leetcode problem: https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
All elements of each string will have an ASCII value in
It is important to notice the hints that this might require a DP solution: the similarities with the edit-distance problem, the fact that the problem is looking for just the minimum sum (could have been maximum sum too) instead of asking for the actual sequence, the fact that any brute-force solution will easily get you to O(2^1000), which is intractable.
You should think about the edit-distance problem and apply the same logic:
Given two strings
s1, s2, find 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.
Note:
0 < s1.length, s2.length <= 1000.[97, 122].It is important to notice the hints that this might require a DP solution: the similarities with the edit-distance problem, the fact that the problem is looking for just the minimum sum (could have been maximum sum too) instead of asking for the actual sequence, the fact that any brute-force solution will easily get you to O(2^1000), which is intractable.
You should think about the edit-distance problem and apply the same logic:
- Build a cost table
- The cost table will indicate the cost to go from s1[0..i] to s2[0..j]. Remember that unlike recursion, you'll be building the solution from smaller strings all the way to the target
- Cost[0,0] = 0
- You also need to initialize the first row and column of the cost, which is straightforward since one of the strings in this case is the empty string
- The induction part although code-wise heavy, it is easy to understand: either you'll try to remove the character from s1, or from s2, or from both, and you'll get the minimum cost among all these three by using the cost table from previously computed string
public class Solution
{
public int MinimumDeleteSum(string s1, string s2)
{
int[,] cost = new int[s1.Length + 1, s2.Length + 1];
//Base
cost[0, 0] = 0;
for (int i = 1; i <= s1.Length; i++) cost[i, 0] = (int)s1[i - 1] + cost[i - 1, 0];
for (int i = 1; i <= s2.Length; i++) cost[0, i] = (int)s2[i - 1] + cost[0, i - 1];
//Induction
for (int i = 1; i <= s1.Length; i++)
{
for (int j = 1; j <= s2.Length; j++)
{
if (s1[i - 1] == s2[j - 1]) cost[i, j] = cost[i - 1, j - 1];
else cost[i, j] = Math.Min(Math.Min(cost[i - 1, j] + s1[i - 1], cost[i, j - 1] + s2[j - 1]), s1[i - 1] + s2[j - 1] + cost[i - 1, j - 1]);
}
}
return cost[s1.Length, s2.Length];
}
}
Very nice! My solution is very similar, although it has O(N) space complexity since we only need a single previous raw instead of entire table:
ReplyDeleteclass Solution {
public:
int minimumDeleteSum(const string& s1, const string& s2) {
vector prev(s2.size()+1);
vector current(s2.size()+1);
for (int i = 0; i < s2.size(); ++i) prev[i+1] = prev[i] + s2[i];
for (int i = 1; i <= s1.size(); ++i) {
current[0] = prev[0] + s1[i-1];
for (int j = 1; j <= s2.size(); ++j) {
current[j] = s1[i-1] == s2[j-1] ? prev[j-1] : min(s1[i-1]+prev[j], s2[j-1]+current[j-1]);
}
swap(current, prev);
}
return prev.back();
}
};
Cheers,
Taras