526互联

[LeetCode] 712. Minimum ASCII Delete Sum for Two Strings

发布时间 2023-08-01 04:45:26作者: CNoodle

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 <= 1000
  • s1 and s2 consist of lowercase English letters.

两个字符串的最小ASCII删除和。

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是动态规划。这道题属于动态规划里面的背包问题，思路几乎跟1143题很像。这里我直接给代码。

时间

空间

Java实现 - 自上而下

 1 class Solution {
 2     int[][] memo;
 3 
 4     public int minimumDeleteSum(String s1, String s2) {
 5         int m = s1.length();
 6         int n = s2.length();
 7         memo = new int[m][n];
 8         for (int[] row : memo) {
 9             Arrays.fill(row, -1);
10         }
11         return dp(s1, 0, s2, 0);
12     }
13 
14     private int dp(String s1, int i, String s2, int j) {
15         int res = 0;
16         // base case
17         if (i == s1.length()) {
18             while (j < s2.length()) {
19                 res += s2.charAt(j++);
20             }
21             return res;
22         }
23 
24         if (j == s2.length()) {
25             while (i < s1.length()) {
26                 res += s1.charAt(i++);
27             }
28             return res;
29         }
30 
31         if (memo[i][j] != -1) {
32             return memo[i][j];
33         }
34 
35         if (s1.charAt(i) == s2.charAt(j)) {
36             memo[i][j] = dp(s1, i + 1, s2, j + 1);
37         } else {
38             memo[i][j] = Math.min(
39                 s1.charAt(i) + dp(s1, i + 1, s2, j),
40                 s2.charAt(j) + dp(s1, i, s2, j + 1)
41             );
42         }
43         return memo[i][j];
44     }
45 }
46 
47 // dp自上而下, dfs + memo

 

Java实现 - 自下而上

 1 class Solution {
 2     public int minimumDeleteSum(String s1, String s2) {
 3         int m = s1.length();
 4         int n = s2.length();
 5         int[][] dp = new int[m + 1][n + 1];
 6         // base case
 7         // 一个字符为空，代价就是删除另一个字符里所有的字母
 8         for (int i = 1; i <= m; i++) {
 9             dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
10         }
11         for (int j = 1; j <= n; j++) {
12             dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
13         }
14 
15         // normal case
16         for (int i = 1; i <= m; i++) {
17             for (int j = 1; j <= n; j++) {
18                 int c1 = s1.charAt(i - 1);
19                 int c2 = s2.charAt(j - 1);
20                 if (c1 == c2) {
21                     dp[i][j] = dp[i - 1][j - 1];
22                 } else {
23                     dp[i][j] = Math.min(
24                         dp[i][j - 1] + c2,
25                         dp[i - 1][j] + c1
26                     );
27                 }
28             }
29         }
30         return dp[m][n];
31     }
32 }
33 
34 // dp自下而上

 

LeetCode 题目总结