leetcode
leetcode 601 ~ 650
两个字符串的最小ASCII删除和

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

难度:

标签:

题目描述

代码结果

运行时间: 263 ms, 内存: 16.8 MB


/*
 * Problem: Given two strings s1 and s2, return the minimum ASCII sum of deleted characters to make two strings equal.
 * Approach: We use dynamic programming, utilizing Java Streams to simplify operations. The main logic remains similar to the above Java solution, but we use streams to fill the dp array and calculate the minimum deletion sum.
 */
import java.util.stream.IntStream;
public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        IntStream.range(1, m + 1).forEach(i -> dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1));
        IntStream.range(1, n + 1).forEach(j -> dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1));
        IntStream.range(1, m + 1).forEach(i ->
            IntStream.range(1, n + 1).forEach(j -> {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
                }
            })
        );
        return dp[m][n];
    }
}
 

解释

方法:

这个题解的思路是先求出两个字符串的最长公共子序列(Longest Common Subsequence, LCS),然后计算出两个字符串所有字符的 ASCII 码值之和,最后用两个字符串的 ASCII 码值之和减去 2 倍 LCS 的 ASCII 码值之和,得到删除的最小 ASCII 码值之和。求 LCS 的过程使用了动态规划,dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 的 ASCII 码值之和。

时间复杂度:

O(mn)

空间复杂度:

O(mn)

代码细节讲解

🦆
为什么在计算两个字符串的最长公共子序列时,选择使用动态规划方法?
动态规划方法是解决最长公共子序列(LCS)问题的经典方法,因为LCS问题具有最优子结构和重叠子问题的特性。最优子结构意味着问题的最优解可以从其子问题的最优解构建。重叠子问题意味着在计算过程中,会多次解决相同的子问题。动态规划通过构建一个表格来一次性解决每个子问题,并存储其结果,避免了重复计算,从而提高了效率。
🦆
在动态规划数组dp的定义中,dp[i][j]表示的是text1[:i]和text2[:j]的LCS的ASCII码值之和,而不是长度。这种表示方式有什么特别的优势吗?
将dp[i][j]定义为text1[:i]和text2[:j]的LCS的ASCII码值之和而非仅仅是长度,提供了更多信息和灵活性。这种定义直接关联到问题的最终目标——最小化要删除的字符的ASCII值总和。通过这种方式,我们可以直接从dp数组中获得所需的LCS ASCII值之和,而无需重新遍历字符串来计算ASCII值,从而效率更高,代码更简洁。
🦆
若字符不相等时,你选择从dp[i-1][j]和dp[i][j-1]中取最大值,这种方法是否确保了最优解?
是的,这种方法确保了最优解。在动态规划中,当字符text1[j-1]和text2[i-1]不相等时,我们需要决定是忽略text1的这个字符还是text2的这个字符,以维持最大的LCS ASCII值之和。通过比较dp[i-1][j](忽略text2的字符)和dp[i][j-1](忽略text1的字符)并选择两者中的最大值,我们确保了在当前字符不匹配的情况下,仍然保持最大的ASCII值之和,从而保证了结果的最优性。
🦆
在实际代码实现中,dp数组的大小为(m+1)*(n+1),这样初始化的原因是什么?
dp数组的大小设置为(m+1)*(n+1)是为了方便处理边界条件,其中m和n分别是text1和text2的长度。在动态规划中,我们通常需要考虑空字符串作为一个有效的子序列。dp[i][0]和dp[0][j]分别表示text1的前i个字符和空字符串以及空字符串和text2的前j个字符的LCS的ASCII值之和。初始化这些值为0,可以使我们在填充dp表时,不需要对i=0或j=0的情况做特殊处理,从而简化代码实现。

相关问题

编辑距离

给你两个单词 word1 和 word2请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

 

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

 

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1word2 由小写英文字母组成

最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7]子序列

 

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

 

提示:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

 

进阶:

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

两个字符串的删除操作

给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数

每步 可以删除任意一个字符串中的一个字符。

 

示例 1:

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ,第二步将 "eat "变为 "ea"

示例  2:

输入:word1 = "leetcode", word2 = "etco"
输出:4

 

提示:

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母