哔哩哔哩0829秋招笔试真题解析

来自公众号：吴师兄学算法

题目描述

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

0 <= s1.length, s2.length <= 1000

s1和s2由小写英文字母组成.

输入描述

本题为LeetCode核心代码模式，传入两个参数s1和s2，为两个字符串。

输出描述

返回一个整数，为使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例一

输入

s1 = "sea"
s2 = "eat"

输出

231

说明

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

示例二

输入

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 的结果，比答案更大。

解题思路

注意，本题为LeetCode712. 两个字符串的最小ASCII删除和原题。属于经典的LCS问题的变式。

代码

Python

# 题目：Bilibili2023秋招-两个字符串的最小ASCII删除和
# 作者：闭着眼睛学数理化
# 算法：DP-LCS问题变式
# 代码有看不懂的地方请直接在群上提问

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        # 分别获得s1和s2的长度
        n, m = len(s1), len(s2)
        # 构建大小为(n+1)*(m+1)的dp数组
        # dp[i][j]表示，令
        # 以s1[i-1]为结尾的字串s1[:i]
        # 以s2[j-1]为结尾的字串s2[:j]
        # 两者完全相同所需删除字符的ASCII值的最小和
        dp = [[0] * (m+1) for _ in range(n+1)]
        # 初始化dp数组中第1行、第1列的情况
        for i in range(1, n+1):
            dp[i][0] = dp[i-1][0] + ord(s1[i-1])
        for j in range(1, m+1):
            dp[0][j] = dp[0][j-1] + ord(s2[j-1])
        for i in range(1, n+1):
            for j in range(1, m+1):
                ch1, ch2 = s1[i-1], s2[j-1]
                # 若两个结尾字符不相等，则在以下三种情况中挑出最小值赋值给dp[i][j]
                # 1. 同时删除s1[i-1]和s2[j-1]，那么从dp[i-1][j-1]转移过来，为ord(ch1) + ord(ch2) + dp[i-1][j-1]
                # 2. 只删除s1[i-1]，保留s2[j-1]，那么从dp[i-1][j]转移过来，为ord(ch1) + dp[i-1][j]
                # 3. 只删除s2[j-1]，保留s1[i-1]，那么从dp[i][j-1]转移过来，为ord(ch2) + dp[i][j-1]
                if ch1 != ch2:
                    dp[i][j] = min(ord(ch1) + ord(ch2) + dp[i-1][j-1], ord(ch1) + dp[i-1][j], ord(ch2) + dp[i][j-1])
                # 若两个结尾字符相等，则无需做任何删除
                # 直接在dp[i-1][j-1]中延长过来即可
                else:
                    dp[i][j] = dp[i-1][j-1]
        
        return dp[-1][-1]

Java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n+1][m+1];
        
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i-1][0] + (int)s1.charAt(i-1);
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = dp[0][j-1] + (int)s2.charAt(j-1);
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char ch1 = s1.charAt(i-1);
                char ch2 = s2.charAt(j-1);
                if (ch1 != ch2) {
                    dp[i][j] = Math.min((int)ch1 + (int)ch2 + dp[i-1][j-1], Math.min((int)ch1 + dp[i-1][j], (int)ch2 + dp[i][j-1]));
                } else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        
        return dp[n][m];
    }
}

C++

class Solution {
public:
    int minimumDeleteSum(std::string s1, std::string s2) {
        int n = s1.length();
        int m = s2.length();
        std::vector<std::vector<int>> dp(n+1, std::vector<int>(m+1, 0));

        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i-1][0] + (int)s1[i-1];
        }

        for (int j = 1; j <= m; j++) {
            dp[0][j] = dp[0][j-1] + (int)s2[j-1];
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char ch1 = s1[i-1];
                char ch2 = s2[j-1];
                if (ch1 != ch2) {
                    dp[i][j] = min(ch1 + ch2 + dp[i-1][j-1], min(ch1 + dp[i-1][j], ch2 + dp[i][j-1]));
                } else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        
        return dp[n][m];
    }
};

时空复杂度

时间复杂度：O(NM)。双重循环所花费的时间复杂度。

空间复杂度：O(NM)。dp数组所占空间。

END