583. Delete Operation for Two Strings

🟠   🔖  字符串 动态规划  🔗 LeetCode

题目

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.

题目大意

给定两个单词 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. Make Three Strings Equal

- [72. 编辑距离](https://leetcode.com/problems/edit-distance)
- [712. 两个字符串的最小 ASCII 删除和](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings)
- [1143. 最长公共子序列](https://leetcode.com/problems/longest-common-subsequence)
- [2937. Make Three Strings Equal](https://leetcode.com/problems/make-three-strings-equal)