🧶 初学者友好指南《Minimum ASCII Delete Sum for Two Strings》 – LeetCode 712（C++、Python、JavaScript）

Source: Dev.to

问题概述

给定：

• 两个字符串，s1 和 s2。

你的目标：

• 找到使两个字符串相同所需删除字符的 ASCII 总和的最小值。

直觉

这个问题是 最长公共子序列（LCS） 或 编辑距离 问题的一种变体。核心思路是对每一对字符决定是保留它们还是删除它们，以使两个字符串最终相等。

我们使用 动态规划（DP） 并结合记忆化搜索来探索这些选择：

1. 基准情况 – 如果已经到达其中一个字符串的末尾，使两个字符串相等的唯一办法是删除另一个字符串中剩余的所有字符。我们把这些字符的 ASCII 值相加，作为代价返回。
2. 匹配 – 如果字符 s1[i] 与 s2[j] 相同，保留它们的代价为 0。我们只需移动到下一对字符。
3. 不匹配 – 如果它们不相同，我们有两种主要选择：
   • 删除 s1[i]（支付它的 ASCII 值），然后将剩余的 s1 与当前的 s2 进行比较。
   • 删除 s2[j]（支付它的 ASCII 值），然后将当前的 s1 与剩余的 s2 进行比较。
4. 优化 – 我们始终选择能够得到最小总和的路径。通过在二维数组（dp）中存储结果，避免对同一子问题进行多次计算。

代码块

C++ 解法

class Solution {
public:
    int helper(string& s1, string& s2, int i, int j, vector>& dp) {
        int n = s1.size();
        int m = s2.size();

        // If s1 is exhausted, delete remaining characters of s2
        if (i == n) {
            int sum = 0;
            for (int k = j; k > dp(n, vector(m, -1));
        return helper(s1, s2, 0, 0, dp);
    }
};

Python 解法

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        dp = [[-1] * m for _ in range(n)]

        def helper(i, j):
            # Base case: s1 exhausted
            if i == n:
                return sum(ord(c) for c in s2[j:])
            # Base case: s2 exhausted
            if j == m:
                return sum(ord(c) for c in s1[i:])

            if dp[i][j] != -1:
                return dp[i][j]

            if s1[i] == s2[j]:
                dp[i][j] = helper(i + 1, j + 1)
            else:
                # Compare cost of deleting from s1 vs deleting from s2
                delete_s1 = ord(s1[i]) + helper(i + 1, j)
                delete_s2 = ord(s2[j]) + helper(i, j + 1)
                dp[i][j] = min(delete_s1, delete_s2)

            return dp[i][j]

        return helper(0, 0)

JavaScript 解法

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
    const n = s1.length;
    const m = s2.length;
    const dp = Array.from({ length: n }, () => Array(m).fill(-1));

    function helper(i, j) {
        // Base case: s1 exhausted
        if (i === n) {
            let sum = 0;
            for (let k = j; k < m; ++k) sum += s2.charCodeAt(k);
            return sum;
        }
        // Base case: s2 exhausted
        if (j === m) {
            let sum = 0;
            for (let k = i; k < n; ++k) sum += s1.charCodeAt(k);
            return sum;
        }

        if (dp[i][j] !== -1) return dp[i][j];

        if (s1[i] === s2[j]) {
            dp[i][j] = helper(i + 1, j + 1);
        } else {
            // Minimum of deleting s1[i] or s2[j]
            const deleteS1 = s1.charCodeAt(i) + helper(i + 1, j);
            const deleteS2 = s2.charCodeAt(j) + helper(i, j + 1);
            dp[i][j] = Math.min(deleteS1, deleteS2);
        }
        return dp[i][j];
    }

    return helper(0, 0);
};

关键要点

• 记忆化（Memoization）: 通过在二维数组中缓存结果，我们将时间复杂度从指数级降低到 O(n · m)，其中 n 和 m 是两个字符串的长度。
• ASCII 映射: 字符值不仅仅是标签。使用 Python 的 ord() 或 JavaScript 的 charCodeAt() 可以将文本视为数值数据以进行优化。
• 决策树: 这个问题教会你如何将选择（删除 s1 与删除 s2）建模为递归调用的树，并通过动态规划高效剪枝。

最终思考

最小 ASCII 删除和问题是一个经典示例，展示了如何将看似简单的字符串操作任务转化为动态规划挑战。通过理解其底层的 LCS 风格递推关系并应用记忆化，你可以在任何语言中高效地解决它。

对标准算法进行细微调整即可改变其应用场景。在实际的软件工程中，这一逻辑被用于 Bioinformatics 中对 DNA 序列进行比对，或在 Version Control Systems（例如 Git）中计算两个文件版本之间的 diff。掌握这些加权字符串问题将使你在构建搜索引擎或比较工具时更加高效。