1092. 最短公共超序列

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

题目

Given two strings str1 and str2, return the shortest string that has bothstr1 andstr2 assubsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Example 1:

Input: str1 = "abac", str2 = "cab"

Output: "cabac"

Explanation:

str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".

str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".

The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"

Output: "aaaaaaaa"

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

题目大意

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：

输入： str1 = "abac", str2 = "cab"

输出： "cabac"

解释：

str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。

str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。

最终我们给出的答案是满足上述属性的最短字符串。

示例 2：

输入： str1 = "aaaaaaaa", str2 = "aaaaaaaa"

输出： "aaaaaaaa"

提示：

• 1 <= str1.length, str2.length <= 1000
• str1 和 str2 都由小写英文字母组成。

解题思路

1. 找出 str1 和 str2 的最长公共子序列（LCS）：

   • 设 dp[i][j] 为 str1[0...i-1] 和 str2[0...j-1] 的 LCS 长度。

   • dp[i][j] 的状态转移：

     • 如果 str1[i-1] == str2[j-1]：

       dp[i][j] = 1 + dp[i-1][j-1]

     • 如果 str1[i-1] ≠ str2[j-1]：

       dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2. 通过 dp 数组回溯构造 SCS：

   • 若 str1[i-1] == str2[j-1]，加入 SCS，并向左上角移动 (i-1, j-1)。
   • 若 dp[i-1][j] > dp[i][j-1]，加入 str1[i-1]，向上移动 (i-1, j)。
   • 否则，加入 str2[j-1]，向左移动 (i, j-1)。
   • 当 i 或 j 还有剩余字符时，全部加入 SCS。

复杂度分析

• 时间复杂度：O(m * n)，构造 dp 数组。
• 空间复杂度：O(m * n)，存储 dp 数组。

代码

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var shortestCommonSupersequence = function (str1, str2) {
	const m = str1.length,
		n = str2.length;
	let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0));

	// 计算最长公共子序列 (LCS)
	for (let i = 1; i <= m; i++) {
		for (let j = 1; j <= n; j++) {
			if (str1[i - 1] === str2[j - 1]) {
				dp[i][j] = 1 + dp[i - 1][j - 1];
			} else {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	// 通过 dp 反向构造 SCS
	let i = m,
		j = n;
	let result = [];
	while (i > 0 && j > 0) {
		if (str1[i - 1] === str2[j - 1]) {
			result.push(str1[i - 1]);
			i--;
			j--;
		} else if (dp[i - 1][j] > dp[i][j - 1]) {
			result.push(str1[i - 1]);
			i--;
		} else {
			result.push(str2[j - 1]);
			j--;
		}
	}

	// 处理剩余字符
	while (i > 0) {
		result.push(str1[i - 1]);
		i--;
	}
	while (j > 0) {
		result.push(str2[j - 1]);
		j--;
	}

	return result.reverse().join('');
};

相关题目

题号	标题	题解	标签	难度	力扣
1143	最长公共子序列	[✓]	字符串 动态规划	🟠	🀄️ 🔗
2800	包含三个字符串的最短字符串		贪心 字符串 枚举	🟠	🀄️ 🔗