两个字符串的最小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)
代码细节讲解
🦆
为什么在计算两个字符串的最长公共子序列时,选择使用动态规划方法?
▷🦆
在动态规划数组dp的定义中,dp[i][j]表示的是text1[:i]和text2[:j]的LCS的ASCII码值之和,而不是长度。这种表示方式有什么特别的优势吗?
▷🦆
若字符不相等时,你选择从dp[i-1][j]和dp[i][j-1]中取最大值,这种方法是否确保了最优解?
▷🦆
在实际代码实现中,dp数组的大小为(m+1)*(n+1),这样初始化的原因是什么?
▷相关问题
编辑距离
给你两个单词 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
word1
和word2
由小写英文字母组成
最长递增子序列
给你一个整数数组 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))
吗?