跳至主要內容

583. 两个字符串的删除操作


583. 两个字符串的删除操作

🟠   🔖  字符串 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

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 and word2 consist of only lowercase English letters.

题目大意

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

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

word1word2 只包含小写英文字母。

解题思路

题目要求计算将两个字符串变得相同的最少删除次数,而这两个字符串最后被删除的结果,其实就是它们的最长公共子序列。

第 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;
};

相关题目

题号标题题解标签难度力扣
72编辑距离[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
712两个字符串的最小ASCII删除和[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
1143最长公共子序列[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
2937使三个字符串相等字符串🟢🀄️open in new window 🔗open in new window