583. 两个字符串的删除操作
583. 两个字符串的删除操作
题目
Given two strings word1
and word2
, return the minimum number of steps required to make word1
and word2
the same.
In one step , you can delete exactly one character in either string.
Example 1:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Example 2:
Input: word1 = "leetcode", word2 = "etco"
Output: 4
Constraints:
1 <= word1.length, word2.length <= 500
word1
andword2
consist of only lowercase English letters.
题目大意
给定两个单词 word1
和 word2
,返回使得 word1
和 word2
相同 所需的 最小步数 。
每步 可以删除任意一个字符串中的一个字符。
word1
和 word2
只包含小写英文字母。
解题思路
题目要求计算将两个字符串变得相同的最少删除次数,而这两个字符串最后被删除的结果,其实就是它们的最长公共子序列。
在 第 1143 题 中,我们计算了两个字符串的最长公共子序列的长度(有递归和 DP table 两种方法)。
那么,要计算删除的次数,就可以通过最长公共子序列的长度推导出来:
var minDistance = function (s1, s2) {
const m = s1.length;
const n = s2.length;
// 计算最长公共子序列的长度
const lcs = longestCommonSubsequence(s1, s2);
return m - lcs + n - lcs;
};
代码
动态规划-递归
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function (word1, word2) {
const m = word1.length;
const n = word2.length;
let dp = new Array(m).fill(-1).map((i) => new Array(n).fill(-1));
const helper = (i, j) => {
if (i == -1 || j == -1) return 0;
if (dp[i][j] != -1) return dp[i][j];
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = 1 + helper(i - 1, j - 1);
} else {
dp[i][j] = Math.max(helper(i, j - 1), helper(i - 1, j));
}
return dp[i][j];
};
// 计算最长公共子序列的长度
const lcs = helper(m - 1, n - 1);
return m - lcs + n - lcs;
};
动态规划-DP table
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function (word1, word2) {
const m = word1.length;
const n = word2.length;
const dp = new Array(m + 1).fill(0).map((i) => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i] == word2[j]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
const lcs = dp[m][n];
return m - lcs + n - lcs;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
72 | 编辑距离 | [✓] | 字符串 动态规划 | |
712 | 两个字符串的最小ASCII删除和 | [✓] | 字符串 动态规划 | |
1143 | 最长公共子序列 | [✓] | 字符串 动态规划 | |
2937 | 使三个字符串相等 | 字符串 |