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

🟠   🔖  字符串 动态规划  🔗 力扣 LeetCode

题目

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"

Output: 231

Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.

Deleting "t" from "eat" adds 116 to the sum.

At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"

Output: 403

Explanation: Deleting "dee" from "delete" to turn the string into "let",

adds 100[d] + 101[e] + 101[e] to the sum.

Deleting "e" from "leet" adds 101[e] to the sum.

At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.

If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Constraints:

• 1 <= s1.length, s2.length <= 1000
• s1 and s2 consist of lowercase English letters.

题目大意

给定两个字符串 s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

s1 和 s2 由小写英文字母组成

示例 1:

输入: s1 = "sea", s2 = "eat"

输出: 231

解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。在 "eat" 中删除 "t" 并将 116 加入总和。

结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"

输出: 403

解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。

结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。

如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

解题思路

这道题和 第 1143 题 和 第 583 题 非常相似， 第 1143 题 是求最长公共子序列的长度， 第 583 题 是在求最长公共子序列长度的基础上计算删除字符的次数，本题是计算删除字符的 ASCII 值最小和。

解题思路还是一样的，只不过 base case 需要修改一下，计算最长公共子序列长度时，如果一个字符串为空，那么最长公共子序列长度必然是 0；但是这道题如果一个字符串为空，另一个字符串必然要被全部删除，所以需要计算另一个字符串所有字符的 ASCII 码之和。

关于状态转移，当 s1[i] 和 s2[j] 相同时不需要删除，不同时需要删除，所以可以利用 helper 函数计算两种情况，得出最优的结果。

其他的大同小异，就不具体展开了。

代码

动态规划-递归

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
	const m = s1.length;
	const n = s2.length;

	let dp = new Array(m).fill(-1).map((i) => new Array(n).fill(-1));

	// base case
	const helper = (i, j) => {
		let res = 0;

		// 如果 s1 到头了，那么 s2 剩下的都得删除
		if (i == -1) {
			for (; j >= 0; j--) {
				res += s2.charCodeAt(j);
			}
			return res;
		}

		// 如果 s2 到头了，那么 s1 剩下的都得删除
		if (j == -1) {
			for (; i >= 0; i--) {
				res += s1.charCodeAt(i);
			}
			return res;
		}

		if (dp[i][j] != -1) return dp[i][j];

		if (s1.charAt(i) == s2.charAt(j)) {
			// s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
			dp[i][j] = helper(i - 1, j - 1);
		} else {
			// s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
			dp[i][j] = Math.min(
				s1.charCodeAt(i) + helper(i - 1, j),
				s2.charCodeAt(j) + helper(i, j - 1)
			);
		}
		return dp[i][j];
	};

	return helper(m - 1, n - 1);
};

动态规划-DP table

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
	const m = s1.length;
	const n = s2.length;
	let dp = new Array(m + 1).fill(0).map((i) => new Array(n + 1).fill(0));
	// base case
	// 当 s2 为空串（即 j = 0）时，dp[i][0]为 s1[0..i - 1]的 ASCII 值之和
	for (let i = 1; i <= m; i++) {
		dp[i][0] = s1.charCodeAt(i - 1) + dp[i - 1][0];
	}

	// 当 s1 为空串（即 i = 0）时，dp[0][j]为 s2[0..j - 1]的 ASCII 值之和
	for (let j = 1; j <= n; j++) {
		dp[0][j] = s2.charCodeAt(j - 1) + dp[0][j - 1];
	}

	for (let i = 1; i <= m; i++) {
		for (let j = 1; j <= n; j++) {
			if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
				// s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
				dp[i][j] = dp[i - 1][j - 1];
			} else {
				// s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
				dp[i][j] = Math.min(
					s1.charCodeAt(i - 1) + dp[i - 1][j],
					s2.charCodeAt(j - 1) + dp[i][j - 1]
				);
			}
		}
	}
	return dp[m][n];
};

相关题目

题号	标题	题解	标签	难度
72	编辑距离	[✓]	字符串 动态规划
300	最长递增子序列	[✓]	数组 二分查找 动态规划
583	两个字符串的删除操作	[✓]	字符串 动态规划