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

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 携程 B站
标签
字符串 动态规划

题目描述

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

image-20260928223806959

题意分析

可以从两个字符串中删除字符，保留字符的相对顺序不变，最终使两串内容完全相同。每删除一个字符，就支付它的 ASCII 值，要求总费用最小。

不同字符的费用不同，因此只求最少删除几个字符或最长公共子序列的长度还不够；需要在选择保留、删除时直接比较费用。题目只包含小写英文字母，代码读取的字符值就等于所需的 ASCII 值。

解法：动态规划状态转移

核心思路

[!blue]

设两串长度为 m、n。定义 dp[i][j] 为将后缀 s1[i..m-1] 与 s2[j..n-1] 删除成相同字符串的最小费用。下标表示还没处理的第一个字符，所以最终答案是 dp[0][0]。

先确定空后缀的边界：两侧都为空时费用是 $0$；只有一侧为空时，另一侧没有字符可以保留配对，只能全部删除。因此 dp[i][n] 是 s1 从 i 起的字符值总和，dp[m][j] 是 s2 从 j 起的字符值总和。

两侧都有字符时，比较当前首字符：

  • 相同：可以保留这两个字符并让它们配对，不付费用，问题缩小为 dp[i + 1][j + 1]。这样不会损失最优方案：若一个方案把这两个首字符都删了，可以把它们一起保留在公共串开头；若用首字符与另一串后面的同字符配对，也可以把这次配对移到当前两个首字符，后续配对顺序不受影响，费用不会增加。
  • 不同：两者不能同时成为剩余字符串的首字符，至少要删除其中一个。删除 s1[i] 的费用是 s1[i] + dp[i + 1][j]；删除 s2[j] 的费用是 s2[j] + dp[i][j + 1]，取较小者。两者都删的方案已经包含在先删一侧、再由后续状态删另一侧的过程中，无需额外列一种转移。

每个状态依赖下方、右方或右下方的状态，所以先填最后一行、最后一列，再让 i、j 都从大到小遍历。这样计算当前格时，所需子问题已经完成；所有状态填完后，dp[0][0] 就包含两串全部字符的最优选择。

解题步骤

  1. 创建 (m + 1) × (n + 1) 的状态表，dp[m][n] 保持为 $0$。
  2. 倒序累加各自后缀的字符值，填好 dp[i][n] 与 dp[m][j]。
  3. 两维倒序遍历：当前字符相同就继承右下方；不同就比较删除左串或右串当前字符的总费用。
  4. 返回 dp[0][0]。

代码实现

class Solution {
    // 若字符相等则继承 dp[i+1][j+1]，否则取删除一边的最小代价。
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = m - 1; i >= 0; i--) {
            // 另一侧为空，当前后缀只能全部删除
            dp[i][n] = dp[i + 1][n] + s1.charAt(i);
        }

        for (int j = n - 1; j >= 0; j--) {
            dp[m][j] = dp[m][j + 1] + s2.charAt(j);
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    // 相同首字符保留配对，不增加删除费用
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    int del1 = s1.charAt(i) + dp[i + 1][j];
                    int del2 = s2.charAt(j) + dp[i][j + 1];

                    dp[i][j] = Math.min(del1, del2);
                }
            }
        }

        return dp[0][0];
    }
}

func minimumDeleteSum(s1 string, s2 string) int {
    // 若字符相等则继承 dp[i+1][j+1]，否则取删除一边的最小代价。
    m := len(s1)
    n := len(s2)
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }

    for i := m - 1; i >= 0; i-- {
        // 另一侧为空，当前后缀只能全部删除
        dp[i][n] = dp[i+1][n] + int(s1[i])
    }
    for j := n - 1; j >= 0; j-- {
        dp[m][j] = dp[m][j+1] + int(s2[j])
    }

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if s1[i] == s2[j] {
                // 相同首字符保留配对，不增加删除费用
                dp[i][j] = dp[i+1][j+1]
            } else {
                del1 := int(s1[i]) + dp[i+1][j]
                del2 := int(s2[j]) + dp[i][j+1]
                if del1 < del2 {
                    dp[i][j] = del1
                } else {
                    dp[i][j] = del2
                }
            }
        }
    }

    return dp[0][0]
}

复杂度分析

  • 时间复杂度：$O((m+1)(n+1))$，包含空后缀边界的初始化。
  • 空间复杂度：$O((m+1)(n+1))$，完整后缀状态表。

关键点总结

[!green]

  • 若保留的公共子序列权值为 W，删除费用就是两串字符值总和减去 2W，所以应优化权值而非长度。
  • 两侧都删除的选择已包含在连续单侧删除中。

易错点总结

[!yellow]

  • 边界全部留零，会漏掉另一串仍需删除的字符代价。
  • 使用字母序号而非 ASCII 值，会改变费用。
  • 按正序计算，会读取尚未完成的后缀状态。

相似题目

题目 难度 关联与区别
583. 两个字符串的删除操作 中等 原题每次删除成本为1，本题成本为字符ASCII值，需要把长度目标改成加权保留或删除代价。
1143. 最长公共子序列 中等 可转成最大公共子序列的ASCII权重和，再由两串总权重减去两倍保留权重。
72. 编辑距离 中等 用两个前缀构成二维动态规划状态；本题删除代价改为字符编码之和，该题允许插入删除替换并求最小代价。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/23358158
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！