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

题目描述

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
  示例 1:
  输入: s1 = “sea”, s2 = “eat”
  输出: 231
解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。
在 “eat” 中删除 “t” 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

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

    0 <= s1.length, s2.length <= 1000s1 和 s2 由小写英文字母组成

一、解题关键词

二、解题报告

1.思路分析

2.时间复杂度

3.代码示例

class Solution {public int minimumDeleteSum(String s1, String s2) {int len1 = s1.length(),len2 = s2.length();int [][] dp = new int [len1 + 1][len2 + 1];for(int i = len1 - 1 ; i >= 0;i--){dp[i][len2] = dp[i + 1][len2] + s1.codePointAt(i);}for(int j = len2 - 1; j >= 0; j--){dp[len1][j] = dp[len1][j + 1] + s2.codePointAt(j);}for(int i = len1 - 1;i >= 0;i--){for(int j = len2 - 1; j >= 0;j--){if(s1.charAt(i) == s2.charAt(j)){dp[i][j] = dp[i + 1][j + 1];} else {dp[i][j] = Math.min(dp[i + 1][j] + s1.codePointAt(i),dp[i][j + 1]+ s2.codePointAt(j));}}}return dp[0][0];}
}

2.知识点

动态规划，

---

总结

相同题目

xxx