Leetcode.712 两个字符串的最小ASCII删除和

题目链接

Leetcode.712 两个字符串的最小ASCII删除和 mid

题目描述

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

示例 1:

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

示例 2:

输入: s1 = “delete”, s2 = “leet”
输出: 403
解释: 在 “delete” 中删除 “dee” 字符串变成 “let”，
将 100[d]+101[e]+101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。
结束时，两个字符串都等于 “let”，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 “lee” 或 “eet”，我们会得到 433 或 417 的结果，比答案更大。

提示:

• $0\le s1.length,s2.length\le 1000$
• s1 和 s2 由小写英文字母组成

解法：动态规划

我们定义 $f(i,j)$ 为：使得 s1 的前 $i$ 个字符 和 s2 的前 $j$ 个字符相等所需要删除字符的最小 ASCII 值。

按照定义最终我们要返回的答案就是 $f(m,n)$ ，$m,n$ 分别为 s1 和 s2 中的字符数量。

我们用 $ASCII(x)$ 表示 $x$ 的ASCII值。

• 如果$s1[i-1]=s2[j-1]$，那么 $f(i,j)=f(i-1,j-1)$；
• 如果$s1[i-1]\ne s2[j-1]$，那么既可能选择删除 $s1[i-1]$，此时 $f(i,j)=f(i-1,j)+ASCII(s1[i-1])$；也有可能选择删除 $s2[j-1]$，此时 $f(i,j)=f(i,j-1)+ASCII(s2[j-1])$。所以要取二者的最小值，即最终式子为 f ( i , j ) = m a x { f ( i − 1 , j ) + A S C I I ( s 1 [ i − 1 ] ) , f ( i , j − 1 ) + A S C I I ( s 2 [ j − 1 ] ) } f(i,j) = max \{f(i-1,j) + ASCII(s1[i-1]),f(i,j - 1) + ASCII(s2[j-1]) \} f(i,j)=max{f(i−1,j)+ASCII(s1[i−1]),f(i,j−1)+ASCII(s2[j−1])}。

对于一些特殊情况，我们需要提前处理。对于 $f(i,0)$ ，$f(0,j)$ 我们只能选择删除所有的字符使得 s1 和 s2 都为空。

时间复杂度： $O(n^2)$

C++代码：

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size() , n = s2.size();
        vector<vector<int>> f(m + 1,vector<int>(n + 1));

        for(int i = 1;i <= m;i++) f[i][0] = f[i - 1][0] + static_cast<int>(s1[i - 1]);
        for(int j = 1;j <= n;j++) f[0][j] = f[0][j - 1] + static_cast<int>(s2[j - 1]);

        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(s1[i - 1] == s2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                }
                else{
                    int a = f[i][j - 1] + static_cast<int>(s2[j - 1]);
                    int b = f[i - 1][j] + static_cast<int>(s1[i - 1]);
                    f[i][j] = min(a,b);
                }
            }
        }
        return f[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24