LeetCode 712. 两个字符串的最小 ASCII 删除和：状态压缩优化

整体思路

1. 核心问题与转换

这段代码依然沿用了 '总和 - 最大公共子序列（LCS）权重' 的逆向思维策略。 核心公式保持不变： 最小删除和 = ( s1 总和 + s2 总和 ) − ( LCS 字符 ASCII 和 × 2 )

2. 算法优化：状态压缩（1D DP）

与上一版二维数组解法不同，这里使用了一维数组进行空间优化。

• 空间压缩原理： 在二维 DP 中，计算 dp[i][j] 只需要用到上一行的数据 dp[i-1][...] 和当前行左边的数据 dp[i][j-1]。
  • f[j+1] 在更新前，存储的是上一行对应位置的值（相当于 dp[i-1][j]）。
  • f[j] 在更新后，存储的是当前行左边位置的值（相当于 dp[i][j-1]）。
  • 难点：在于如何获取 dp[i-1][j-1]（左上角的值）。因为在更新 f[j+1] 之前，f[j] 已经被更新为当前行的值了。
  • 解决方案：引入 pre 变量，专门用来暂存上一行对角线位置的值。
• 逻辑流程：
  1. 初始化长度为 m + 1 的数组 f，初始全为 0（代表空串时的公共和）。
  2. 外层循环遍历 s1 的字符 x。
  3. 在内层循环开始前，初始化 pre = 0（代表第 0 列的左上角，即空前缀）。
  4. 内层循环遍历 s2 的索引 j：
     • 先用 temp 保存 f[j+1] 的旧值（即下一轮需要的左上角值）。
     • 根据 x 和 t[j] 是否相等，利用 pre、f[j+1]（旧）、f[j]（新）更新 f[j+1]。
     • 更新 pre = temp，为下一个位置做准备。

完整代码

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        // 1. 计算两字符串初始的总 ASCII 和
        int sum = s1.chars().sum() + s2.chars().sum();
        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int m = t.length;
        // 2. 创建一维 DP 数组
        // f[k] 表示 s1 当前处理到的前缀与 s2 的前 k 个字符的最大公共 ASCII 权重和
        int[] f = new int[m + 1];
        // Java 中 int 数组默认初始化为 0，符合逻辑（空串的公共和为 0）
        // 外层循环：遍历 s1 的每个字符 x
        for (char x : s) {
            // pre 用于维护 "左上角" (diagonal) 的状态
            // 相当于二维 DP 中的 dp[i-1][j-1]
            // 对于每一行的第一个元素，其左上角是 f[0]，始终为 0
            int pre = 0;
            // 内层循环：遍历 s2 的每个位置 j
            for (int j = 0; j < m; j++) {
                // temp 暂存 f[j+1] 在更新前的值
                // 这个值对应二维 DP 中的 dp[i-1][j] (上一行的值)
                // 在下一次循环 (j+1) 时，它将变成 "左上角" (pre)
                int temp = f[j + 1];
                // 状态转移逻辑
                if (x == t[j]) {
                    // 字符匹配：
                    // 当前值 = 左上角值 (pre) + 当前字符 ASCII * 2
                    f[j + 1] = pre + x * 2;
                } else {
                    // 字符不匹配：
                    // 取 "上方" (f[j+1] 旧值) 和 "左方" (f[j] 新值) 的最大值
                    f[j + 1] = Math.max(f[j + 1], f[j]);
                }
                // 更新 pre，将当前的旧值传递给下一次内层循环作为左上角使用
                pre = temp;
            }
        }
        // 3. 计算结果
        // 总和 - 最大保留部分的和
        return sum - f[m];
    }
}

时空复杂度

1. 时间复杂度：O(N \times M)

• 计算依据：
  • 双重循环结构没有改变。
  • 外层循环执行 N 次（s1 的长度），内层循环执行 M 次（s2 的长度）。
  • 内部操作均为 O(1)。
• 结论：O(N \times M)。

2. 空间复杂度：O(M)

• 计算依据：
  • 这是此代码的主要亮点。
  • 我们将原本 (N + 1) × (M + 1) 的二维数组压缩为了长度为 M + 1 的一维数组 f。
  • 额外使用了几个常数变量（pre, temp 等）。
  • 空间消耗仅与 s2 的长度线性相关。
• 结论：O(M)，其中 M 是 s2 的长度。
  • 优化提示：如果 N < M，可以在代码开始前交换 s1 和 s2，使空间复杂度进一步优化为 O(min(N, M))。