LeetCode 712. Minimum ASCII Delete Sum for Two Strings

712.Minimum ASCII Delete Sum for Two Strings（两个字符串的最小ASCII删除和）

链接

https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/

题目

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

示例 1:

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

注意:

0 < s1.length, s2.length <= 1000。
所有字符串中的字符ASCII值在[97, 122]之间。

思路

与前段时间的最小编辑距离相似，这题一看就觉得应该用动态规划，缺什么就定义什么，这边需求最小和，那么就设定数组step[][]，和sc1[]，sc2[]。后两个是输入字符串转换而来，减少运算时间。step[i][j]数组是用于存放s1中前
i 个字母和s2中前 j 个字母的最小删除和。

首先进行初始化，原点的值为0，之后行列就是将前n为清空所需的最小删除和，之后进行二维计算。

此时对于s1中的第 i+1 个字母，和s2中的第 j+1 个字母，进行判断：

如果二者相同，则无需变化，直接 step[ i+1 ][ j+1 ] = step[ i ][ j ] ；
二者不同，就要考虑是删除s1的新字母还是删除s2的新字母，当然，还有两种都删除，

即为 step[ i+1 ][ j+1 ] = Min(num1，num2，num3);

最后得到的step[ i ][ j ]就是最小删除和。

图解

红色加大部分是e，相同，即为左上格子的值；黑色加大是不同的，三选一，找到最小值。

代码


public static int minimumDeleteSum(String s1, String s2) {
  int len1 = s1.length();
  int len2 = s2.length();
  char[] sc1 = s1.toCharArray();
  char[] sc2 = s2.toCharArray();
  int[][] step = new int[len1 + 1][len2 + 1];

  step[0][0] = 0;

  for (int i = 1; i <= len1; i++) {
    step[i][0] = step[i - 1][0] + sc1[i - 1];
  }

  for (int j = 1; j <= len2; j++) {
    step[0][j] = step[0][j - 1] + sc2[j - 1];
  }

  for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
      if (sc1[i - 1] == sc2[j - 1]) {
        step[i][j] = step[i - 1][j - 1];
      } else {
        step[i][j] = Math.min(Math.min(step[i - 1][j] + sc1[i - 1], step[i][j - 1] + sc2[j - 1]),
            step[i - 1][j - 1] + sc1[i - 1] + sc2[j - 1]);

      }
    }
  }

  return step[len1][len2];
}