题目描述

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

给定两个字符串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 <= s1.length, s2.length <= 1000
  • s1 和 s2 由小写英文字母组成

题解——最长公共子序列 (LCS)应用题

本题和583. 两个字符串的删除操作很类似，都是1143. 最长公共子序列的直观应用

思路

理解题意

逆向思维，通过删除ascii码和最小的字符，使两个字符串相同，就等价于找到s1和s2的ascii码最大的公共子序列，答案就是asciiSum1+asciiSum2-2*maxAsciiSum(1&2)，关键在于如何寻找这个特殊的LCS。

贪心

查表可知，'a'的ascii码值为97，'z'的ascii码值为122，2*'a'>'z'，也就是说，长度为n+1的子序列的ascii码和一定大于长度为n的子序列，因此，我们应当贪心地寻找更长的子序列。可以说，最终找到的子序列一定是LCS中的和最大的那一个。所以，我们可以大胆套用LCS的模板，只不过要保存ascii和。

如何求LCS？

具体可参照1143. 最长公共子序列，我在这里简单地提供两种方法，即动态规划以及记忆化搜索。
先从直观的记忆化搜索说起，要寻找s1和s2的最长公共子序列，我们利用一个二维数组储存从s1[i],s2[j]开始能找到的最长公共子序列，对每一个i和j，如果此位置相同，则保留，同时步进；如果此位置不同，步进i或者j，保存最大值。对于1143. 最长公共子序列，可以写出如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//记搜，用一个二维数组记录text1从i开始，text2从j开始能形成的最长公共子序列
class Solution {
public:
    vector<vector<int>> memo;
    string s1,s2;
    int solve(int i,int j)
    {
        if(i>=s1.size()||j>=s2.size())
            return 0;
        if(memo[i][j]!=-1)//搜索过了，直接返回答案
            return memo[i][j];
        else if(s1[i]==s2[j])//如果此时两个字符相等，同时步进，长度为下一个+1
            memo[i][j]=solve(i+1,j+1)+1;
        else//不相等，应是i+1和j+1的最大值
            memo[i][j]=max(solve(i+1,j),solve(i,j+1));
        return memo[i][j];
    }
    int longestCommonSubsequence(string text1, string text2) {
        memo=vector<vector<int>>(text1.size(),vector<int>(text2.size(),-1));
        s1=text1,s2=text2;
        return solve(0,0);//返回i和j都从0开始的值即可
    }
};

将递归改成迭代，就是动态规划的写法了，不多赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                if(text1[i-1] == text2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
};

如上所说，我们要找的仍然是一个特殊的LCS，只不过是ascii和最大的那一个，所以只需要在比较和保存时，把+1改成+ascii即可
两版代码如下

记忆化搜索代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> memo;
    string str1,str2;
    int solve(int i,int j)
    {
        if(i>=str1.size()||j>=str2.size())
            return 0;
        if(memo[i][j]!=-1)//搜索过了，直接返回答案
            return memo[i][j];
        else if(str1[i]==str2[j])//如果此时两个字符相等，同时步进
            memo[i][j]=solve(i+1,j+1)+str1[i];
        else//不相等，应是i+1和j+1的最大值
            memo[i][j]=max(solve(i+1,j),solve(i,j+1));
        return memo[i][j];
    }
    int minimumDeleteSum(string s1, string s2) {
        memo=vector<vector<int>>(s1.size(),vector<int>(s2.size(),-1));
        str1=s1,str2=s2;
        return accumulate(s1.begin(),s1.end(),0)+accumulate(s2.begin(),s2.end(),0)-2*solve(0,0);
    }
};

动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxAsciiSum(string &text1, string &text2) {
        int n = text1.length(), m = text2.length();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                if(text1[i-1] == text2[j-1])
                    dp[i][j] = dp[i-1][j-1] + text1[i-1];
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
    int minimumDeleteSum(string s1, string s2) {
        return accumulate(s1.begin(),s1.end(),0)+accumulate(s2.begin(),s2.end(),0)-2*maxAsciiSum(s1,s2);
    }
};