题目描述

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

样例

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

算法1

(动态规划) $O(n^2)$

f[i][j]的定义为s1[0…i - 1] - s2[0…j - 1]两个字符串相等要删除ASCII码之和的最小值，可分为以下情况：

• 根据含义很好理解其等于下三者的最小值
  • f[i - 1][j] + s1[i - 1]
  • f[i][j - 1] + s2[j - 1]
  • f[i - 1][j - 1] + s1[i - 1] + s2[j - 1]
• 当s1[i - 1] 和 s2[j - 1]相等时，f[i][j] 可转化为 f[i - 1][j - 1]

时间复杂度

$O(n^2)$

参考文献

C++ 代码

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();

        vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));
        f[0][0] = 0;

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

        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                int res = min(f[i - 1][j] + s1[i - 1], f[i][j - 1] + s2[j - 1]);
                if(s1[i - 1] == s2[j - 1]) res = min(res, f[i - 1][j - 1]);
                res = min(f[i - 1][j - 1] + s1[i - 1] + s2[j - 1], res);
                f[i][j] = res;
            }
        }

        return f[n][m];
    }
};