Medium

题目描述

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

示例 1：

输入：s1 = "sea", s2 = "eat"
输出：231
解释：在 "sea" 中删除 "s" 并将其 ASCII 值 115 加到总和中。
在 "eat" 中删除 "t" 并将其 ASCII 值 116 加到总和中。
结束时，两个字符串相等，115 + 116 = 231 是可能的最小和。

示例 2：

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

提示：

  • 1 <= s1.length, s2.length <= 1000
  • s1 和 s2 由小写英文字母组成

解题思路

这是一个经典的动态规划问题，可以看作是最长公共子序列（LCS）的变形。

核心思路： 我们需要找到两个字符串的最大公共子序列，然后删除不在公共子序列中的字符。但这里不是求长度，而是求ASCII值的最小删除和。

状态定义： dp[i][j] 表示使 s1[0...i-1] 和 s2[0...j-1] 相等所需的最小ASCII删除和。

状态转移：

  1. 如果 s1[i-1] == s2[j-1]，字符相同，不需要删除： dp[i][j] = dp[i-1][j-1]

  2. 如果字符不同，有两种选择：

    • 删除 s1[i-1]：dp[i][j] = dp[i-1][j] + s1[i-1]
    • 删除 s2[j-1]：dp[i][j] = dp[i][j-1] + s2[j-1] 取两者中的最小值。

边界条件：

  • dp[0][j]：s1为空，需要删除s2的前j个字符
  • dp[i][0]：s2为空，需要删除s1的前i个字符

时间复杂度O(mn)，空间复杂度O(mn)，其中m、n分别是两个字符串的长度。

代码实现

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        // 初始化边界条件
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i-1][0] + s1[i-1];
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j-1] + s2[j-1];
        }
        
        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j] + s1[i-1], 
                                   dp[i][j-1] + s2[j-1]);
                }
            }
        }
        
        return dp[m][n];
    }
};

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 初始化边界条件
        for i in range(1, m + 1):
            dp[i][0] = dp[i-1][0] + ord(s1[i-1])
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j-1] + ord(s2[j-1])
        
        # 填充dp表
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]),
                                   dp[i][j-1] + ord(s2[j-1]))
        
        return dp[m][n]

public class Solution {
    public int MinimumDeleteSum(string s1, string s2) {
        int m = s1.Length, n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];
        
        // 初始化边界条件
        for (int i = 1; i <= m; i++) {
            dp[i, 0] = dp[i - 1, 0] + s1[i - 1];
        }
        for (int j = 1; j <= n; j++) {
            dp[0, j] = dp[0, j - 1] + s2[j - 1];
        }
        
        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1];
                } else {
                    dp[i, j] = Math.Min(dp[i - 1, j] + s1[i - 1],
                                        dp[i, j - 1] + s2[j - 1]);
                }
            }
        }
        
        return dp[m, n];
    }
}

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function(s1, s2) {
    const m = s1.length;
    const n = s2.length;
    
    // dp[i][j] represents min delete sum to make s1[0...i-1] and s2[0...j-1] equal
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    // Fill first row - delete all characters from s1
    for (let i = 1; i <= m; i++) {
        dp[i][0] = dp[i-1][0] + s1.charCodeAt(i-1);
    }
    
    // Fill first column - delete all characters from s2
    for (let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j-1] + s2.charCodeAt(j-1);
    }
    
    // Fill the rest of the dp table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i-1] === s2[j-1]) {
                // Characters match, no deletion needed
                dp[i][j] = dp[i-1][j-1];
            } else {
                // Take minimum of deleting from s1 or s2
                dp[i][j] = Math.min(
                    dp[i-1][j] + s1.charCodeAt(i-1), // delete from s1
                    dp[i][j-1] + s2.charCodeAt(j-1)  // delete from s2
                );
            }
        }
    }
    
    return dp[m][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要填充m×n的二维数组，每个位置计算为O(1)
空间复杂度O(m×n)使用二维数组存储动态规划状态

注：m和n分别为字符串s1和s2的长度

相关题目