【LeetCode 每日一题】712. 两个字符串的最小ASCII删除和——（解法三）状态压缩

Problem: 712. 两个字符串的最小ASCII删除和

文章目录

• 整体思路
  • 1. 核心问题与转换
  • 2. 算法优化：状态压缩（1D DP）
• 完整代码
• 时空复杂度
  • 1. 时间复杂度： O ( N × M ) O(N \times M) O(N×M)
  • 2. 空间复杂度： O ( M ) O(M) O(M)

整体思路

1. 核心问题与转换

这段代码依然沿用了 “总和 - 最大公共子序列（LCS）权重” 的逆向思维策略。
核心公式保持不变：
最小删除和 = ( s1总和 + s2总和 ) − ( LCS字符ASCII和 × 2 ) \text{最小删除和} = (\text{s1总和} + \text{s2总和}) - (\text{LCS字符ASCII和} \times 2) 最小删除和=(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，为下一个位置做准备。

完整代码

classSolution{publicintminimumDeleteSum(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 =newint[m +1];// Java 中 int 数组默认初始化为 0，符合逻辑（空串的公共和为 0）// 外层循环：遍历 s1 的每个字符 xfor(char x : s){// pre 用于维护 "左上角" (diagonal) 的状态// 相当于二维 DP 中的 dp[i-1][j-1]// 对于每一行的第一个元素，其左上角是 f[0]，始终为 0int pre =0;// 内层循环：遍历 s2 的每个位置 jfor(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 × M ) O(N \times M) O(N×M)

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

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

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