最长公共子序列的变种：最短公共超序列
字数 760 2025-10-26 21:53:33
最长公共子序列的变种：最短公共超序列
题目描述：
给定两个字符串str1和str2，要求找出一个最短的字符串，使得str1和str2都是这个字符串的子序列。返回这个最短公共超序列的长度。
解题过程：
-
问题分析：
- 超序列需要包含str1和str2的所有字符，并保持它们在各自原字符串中的相对顺序
- 最短的情况是充分利用两个字符串的公共部分，让公共子序列只出现一次
-
关键观察：
- 最短公共超序列长度 = len(str1) + len(str2) - 最长公共子序列长度
- 因为公共子序列只需要在超序列中出现一次，可以节省这部分长度
-
动态规划定义：
- 定义dp[i][j]表示str1前i个字符和str2前j个字符的最长公共子序列长度
- i的范围是0到len(str1)，j的范围是0到len(str2)
-
状态转移方程：
- 如果str1[i-1] == str2[j-1]：
dp[i][j] = dp[i-1][j-1] + 1 - 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 如果str1[i-1] == str2[j-1]：
-
初始化：
- dp[0][j] = 0（空字符串与任何字符串的LCS长度为0）
- dp[i][0] = 0（任何字符串与空字符串的LCS长度为0）
-
计算顺序：
- 从左到右，从上到下遍历二维dp表
-
最终结果：
- 最短公共超序列长度 = len(str1) + len(str2) - dp[m][n]
- 其中m = len(str1)，n = len(str2)
示例验证：
str1 = "abcde", str2 = "ace"
最长公共子序列"ace"长度为3
最短公共超序列长度 = 5 + 3 - 3 = 5
实际最短公共超序列可以是"abcde"（包含"ace"）