Leetcode 712: Minimum ASCII Delete Sum for Two Strings
Solution to LeetCode 712: Minimum ASCII Delete Sum for Two Strings Problem
Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make the two strings equal.
Problem
Approach
Steps
Complexity
Input: You are given two strings s1 and s2.
Example: s1 = 'hello', s2 = 'goodbye'
Constraints:
• 1 <= s1.length, s2.length <= 1000
• s1 and s2 consist of lowercase English letters.
Output: Return the minimum sum of ASCII values of deleted characters from both strings to make them equal.
Example: If s1 = 'hello' and s2 = 'goodbye', return 732.
Constraints:
• The returned value will be a non-negative integer.
Goal: To calculate the minimum ASCII sum of deleted characters that need to be removed from both strings to make them equal.
Steps:
• Use dynamic programming (DP) to calculate the minimum deletion sum.
• Iterate through both strings and compare characters.
• For each mismatch, calculate the cost of deleting characters from both strings and update the DP table.
Goal: Ensure that the strings are processed within the given limits.
Steps:
• Both strings will not exceed 1000 characters.
• Strings consist only of lowercase English letters.
Assumptions:
• Both strings will contain only lowercase English letters.
• Both strings are non-empty and have at least one character.
• Input: Example 1: s1 = 'hello', s2 = 'goodbye'
• Explanation: In this example, we calculate the sum of deleted characters from both strings to make them equal. The deletions lead to a sum of 732.
• Input: Example 2: s1 = 'dog', s2 = 'god'
• Explanation: Here, no deletions are needed as both strings are already equal, leading to a sum of 0.
Approach: We use dynamic programming to efficiently calculate the minimum ASCII sum of deleted characters.
Observations:
• The problem can be reduced to finding the longest common subsequence (LCS).
• Once we find the LCS, the characters that are not part of it need to be deleted.
• The solution involves calculating the sum of ASCII values for characters that are not in the LCS.
Steps:
• Initialize a DP table to store the minimum ASCII sum of deleted characters.
• Iterate over both strings and fill the DP table based on character comparisons.
• Return the calculated minimum sum by subtracting twice the LCS sum from the total sum of ASCII values of both strings.
Empty Inputs:
• If one or both strings are empty, the sum will be the sum of ASCII values of the non-empty string.
Large Inputs:
• If the strings are large, ensure that the solution handles them within time limits.
Special Values:
• If the strings are already equal, the minimum sum will be 0.
Constraints:
• Ensure that the DP solution does not exceed time and space limits for large inputs.
string s1, s2;
vector<vector<int>> mem;
int dp(int i, int j) {
if(i == s1.size() || j == s2.size()) return 0;
if(mem[i][j] != -1) return mem[i][j];
int ans = max(dp(i + 1, j), dp(i, j + 1));
if(s1[i] == s2[j]) {
ans = max(ans, dp(i + 1, j + 1) + s1[i]);
}
return mem[i][j] = ans;
}
int minimumDeleteSum(string s1, string s2) {
this->s1 = s1;
this->s2 = s2;
int ans = 0;
for(int i = 0; i < s1.size(); i++)
ans += s1[i];
for(int i = 0; i < s2.size(); i++)
ans += s2[i];
mem.resize(s1.size() + 1, vector<int>(s2.size(), -1));
return ans - 2 * dp(0, 0);
}
1 : Variable Initialization
string s1, s2;
Initialize two strings 's1' and 's2' to hold the input strings.
2 : Variable Initialization
vector<vector<int>> mem;
Create a 2D vector 'mem' to store the memoized results of the dynamic programming approach.
3 : Function Declaration
int dp(int i, int j) {
Define the recursive function 'dp' to compute the minimum delete sum between two strings from index i and j.
4 : Base Case
if(i == s1.size() || j == s2.size()) return 0;
If either string has been fully traversed, return 0 as the base case.
5 : Memoization Check
if(mem[i][j] != -1) return mem[i][j];
Check if the result has already been computed for the current indices i and j.
6 : Recursive Call
int ans = max(dp(i + 1, j), dp(i, j + 1));
Recursively calculate the maximum result by either skipping a character from s1 or s2.
7 : Condition Check
if(s1[i] == s2[j]) {
If the characters at the current indices of s1 and s2 are the same, consider them in the result.
8 : Recursive Call with Match
ans = max(ans, dp(i + 1, j + 1) + s1[i]);
If characters match, include the character value in the result and recursively call the function for the next indices.
9 : Return Memoized Value
return mem[i][j] = ans;
Memoize the result for the current indices i and j to avoid redundant calculations.
10 : End of Function
}
End of the 'dp' recursive function.
11 : Function Declaration
int minimumDeleteSum(string s1, string s2) {
Define the function 'minimumDeleteSum' to compute the result for the two input strings.
12 : Variable Initialization
this->s1 = s1;
Assign the input string 's1' to the class member 's1'.
13 : Variable Initialization
this->s2 = s2;
Assign the input string 's2' to the class member 's2'.
14 : Variable Initialization
int ans = 0;
Initialize a variable 'ans' to accumulate the sum of ASCII values of characters in both strings.
15 : Loop
for(int i = 0; i < s1.size(); i++)
Loop through each character in the first string 's1'.
16 : Sum Calculation
ans += s1[i];
Add the ASCII value of the character in s1 to 'ans'.
17 : Loop
for(int i = 0; i < s2.size(); i++)
Loop through each character in the second string 's2'.
18 : Sum Calculation
ans += s2[i];
Add the ASCII value of the character in s2 to 'ans'.
19 : Vector Resize
mem.resize(s1.size() + 1, vector<int>(s2.size(), -1));
Resize the 'mem' vector to the required size to store the memoization results.
20 : Return Result
return ans - 2 * dp(0, 0);
Return the minimum delete sum by subtracting twice the result of 'dp(0, 0)' from the sum of all ASCII values.
Best Case: O(m + n), where m and n are the lengths of the strings.
Average Case: O(m * n), where m and n are the lengths of the strings.
Worst Case: O(m * n), where m and n are the lengths of the strings.
Description: The time complexity is proportional to the product of the lengths of the two strings.
Best Case: O(m * n), where m and n are the lengths of the strings.
Worst Case: O(m * n), where m and n are the lengths of the strings.
Description: The space complexity is proportional to the size of the DP table, which stores the results for all pairs of indices.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus