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 <= 1000s1 and s2 consist of lowercase English letters.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.
This solution defines a 2D DP table where dp[i][j] represents the minimum ASCII delete sum to make the substrings s1[i:] and s2[j:] equal. We pre-compute the additional cost of deleting each character from the end of the strings and use these results to fill the DP table iteratively. If characters at positions i and j are equal, we take the diagonal value; otherwise, we take the minimum cost of deleting either character.
Java
C++
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.
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.
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.
JavaScript
C
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.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | 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. |
| Recursion with Memoization | Time Complexity: O(m * n) due to memoization reducing the duplicate calculations. |
Minimum ASCII Delete Sum for Two Strings | INTUITIVE | Recursion | Memoization | Leetcode-712 • codestorywithMIK • 4,629 views views
Watch 9 more video solutions →Practice Minimum ASCII Delete Sum for Two Strings with our built-in code editor and test cases.
Practice on FleetCode