寻找两个字符串的最短公共超序列（Shortest Common Supersequence，SCS）长度

字数 2763 2025-12-24 22:35:32

寻找两个字符串的最短公共超序列（Shortest Common Supersequence，SCS）长度

题目描述

给定两个字符串 text1 和 text2，要求返回它们的最短公共超序列（Shortest Common Supersequence，简称 SCS）的长度。
一个字符串的“超序列”是指一个字符串，可以通过删除（或不删除）一些字符而不改变剩余字符的相对顺序，得到原字符串。而“公共超序列”则是一个字符串，它同时是 text1 和 text2 的超序列。我们需要找到所有公共超序列中最短的那个的长度。

示例
输入：text1 = "abac", text2 = "cab"
输出：5
解释：最短公共超序列可以是 "cabac"（长度 5），它同时是 "abac" 和 "cab" 的超序列。
验证：

从 "cabac" 中删除第一个 'c' 得到 "abac"（text1）。
从 "cabac" 中删除第二个 'a' 得到 "cab"（text2）。
没有比 5 更短的公共超序列。

解题过程

这个问题可以看作经典“最长公共子序列（LCS）”问题的延伸。如果已知两个字符串的 LCS 长度，那么最短公共超序列的长度可以直接推导出来。

第一步：理解与 LCS 的关系

设：

m = len(text1), n = len(text2)
lcs_len 是 text1 和 text2 的最长公共子序列长度

思考：要构造一个公共超序列，我们必须包含 text1 的所有字符（按顺序）和 text2 的所有字符（按顺序）。
但是，那些在两个字符串中都出现的字符（即 LCS 中的字符）只需要在超序列中出现一次（因为它们可以同时满足两个序列的要求）。
所以，超序列的总长度等于：

m + n - lcs_len

解释：

先把两个字符串的所有字符都放进来，长度为 m + n。
但 LCS 中的每个字符被重复计算了一次（在 text1 和 text2 中各出现一次），所以减去 lcs_len 即为最短长度。

因此，问题转化为：先求两个字符串的 LCS 长度。

第二步：动态规划求 LCS 长度

我们定义 dp[i][j] 表示 text1 的前 i 个字符（下标 0 到 i-1）和 text2 的前 j 个字符（下标 0 到 j-1）的 LCS 长度。
状态转移方程：

如果 text1[i-1] == text2[j-1]，则这个字符可以加入 LCS：
dp[i][j] = dp[i-1][j-1] + 1
否则，取两种可能中的较大值：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始条件：dp[0][j] = 0, dp[i][0] = 0（空字符串的 LCS 长度为 0）。

第三步：计算最短公共超序列长度

得到 lcs_len = dp[m][n] 后，SCS 长度 = m + n - lcs_len。

第四步：具体例子演算

以 text1 = "abac", text2 = "cab" 为例：

m = 4, n = 3。

步骤1：计算 dp 表（LCS 长度）
初始化 dp 表大小为 (5, 4)，行列分别对应 text1 长度和 text2 长度（含空串）。

逐行计算：

i=1, j=1: text1[0]='a', text2[0]='c'，不同 → dp[1][1] = max(dp[0][1], dp[1][0]) = max(0,0) = 0
i=1, j=2: 'a' vs 'a'，相同 → dp[1][2] = dp[0][1] + 1 = 0 + 1 = 1
i=1, j=3: 'a' vs 'b'，不同 → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0,1) = 1
i=2, j=1: 'b' vs 'c'，不同 → dp[2][1] = max(dp[1][1], dp[2][0]) = max(0,0) = 0
i=2, j=2: 'b' vs 'a'，不同 → dp[2][2] = max(dp[1][2], dp[2][1]) = max(1,0) = 1
i=2, j=3: 'b' vs 'b'，相同 → dp[2][3] = dp[1][2] + 1 = 1 + 1 = 2
i=3, j=1: 'a' vs 'c'，不同 → dp[3][1] = max(dp[2][1], dp[3][0]) = max(0,0) = 0
i=3, j=2: 'a' vs 'a'，相同 → dp[3][2] = dp[2][1] + 1 = 0 + 1 = 1
i=3, j=3: 'a' vs 'b'，不同 → dp[3][3] = max(dp[2][3], dp[3][2]) = max(2,1) = 2
i=4, j=1: 'c' vs 'c'，相同 → dp[4][1] = dp[3][0] + 1 = 0 + 1 = 1
i=4, j=2: 'c' vs 'a'，不同 → dp[4][2] = max(dp[3][2], dp[4][1]) = max(1,1) = 1
i=4, j=3: 'c' vs 'b'，不同 → dp[4][3] = max(dp[3][3], dp[4][2]) = max(2,1) = 2

最终 dp[4][3] = 2，即 LCS 长度为 2（对应 LCS 可以是 "ab" 或 "ac"）。

步骤2：计算 SCS 长度
SCS 长度 = m + n - lcs_len = 4 + 3 - 2 = 5。
与示例一致。

算法复杂度

时间复杂度：O(m * n)，用于填 dp 表。
空间复杂度：可以优化为 O(min(m, n))，因为 dp 递推只需要上一行和当前行。

扩展

如果题目要求输出一个具体的最短公共超序列（而不仅仅是长度），可以在得到 dp 表后通过回溯构造。方法是从 dp[m][n] 开始，根据状态转移反向追踪：

若当前位置字符相同，则将该字符加入结果，并移至左上角 (i-1, j-1)。
否则，选择 dp 值较大的方向移动，并将对应字符串的当前字符加入结果（因为超序列需要包含该字符）。
最终将结果字符串反转即可。

这就是“最短公共超序列长度”问题的完整求解思路，核心在于利用 LCS 来避免重复计算公共部分。

寻找两个字符串的最短公共超序列（Shortest Common Supersequence，SCS）长度题目描述给定两个字符串 text1 和 text2 ，要求返回它们的最短公共超序列（Shortest Common Supersequence，简称 SCS）的长度。一个字符串的“超序列”是指一个字符串，可以通过删除（或不删除）一些字符而不改变剩余字符的相对顺序，得到原字符串。而“公共超序列”则是一个字符串，它同时是 text1 和 text2 的超序列。我们需要找到所有公共超序列中最短的那个的长度。示例输入：text1 = "abac", text2 = "cab" 输出：5 解释：最短公共超序列可以是 "cabac"（长度 5），它同时是 "abac" 和 "cab" 的超序列。验证：从 "cabac" 中删除第一个 'c' 得到 "abac"（text1）。从 "cabac" 中删除第二个 'a' 得到 "cab"（text2）。没有比 5 更短的公共超序列。解题过程这个问题可以看作经典“最长公共子序列（LCS）”问题的延伸。如果已知两个字符串的 LCS 长度，那么最短公共超序列的长度可以直接推导出来。第一步：理解与 LCS 的关系设： m = len(text1) , n = len(text2) lcs_len 是 text1 和 text2 的最长公共子序列长度思考：要构造一个公共超序列，我们必须包含 text1 的所有字符（按顺序）和 text2 的所有字符（按顺序）。但是，那些在两个字符串中都出现的字符（即 LCS 中的字符）只需要在超序列中出现一次（因为它们可以同时满足两个序列的要求）。所以，超序列的总长度等于：解释：先把两个字符串的所有字符都放进来，长度为 m + n 。但 LCS 中的每个字符被重复计算了一次（在 text1 和 text2 中各出现一次），所以减去 lcs_len 即为最短长度。因此，问题转化为：先求两个字符串的 LCS 长度。第二步：动态规划求 LCS 长度我们定义 dp[i][j] 表示 text1 的前 i 个字符（下标 0 到 i-1）和 text2 的前 j 个字符（下标 0 到 j-1）的 LCS 长度。状态转移方程：如果 text1[i-1] == text2[j-1] ，则这个字符可以加入 LCS： dp[i][j] = dp[i-1][j-1] + 1 否则，取两种可能中的较大值： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 初始条件： dp[0][j] = 0 , dp[i][0] = 0 （空字符串的 LCS 长度为 0）。第三步：计算最短公共超序列长度得到 lcs_len = dp[m][n] 后，SCS 长度 = m + n - lcs_len 。第四步：具体例子演算以 text1 = "abac", text2 = "cab" 为例： m = 4, n = 3。步骤1：计算 dp 表（LCS 长度）初始化 dp 表大小为 (5, 4)，行列分别对应 text1 长度和 text2 长度（含空串）。逐行计算： i=1, j=1: text1[ 0]='a', text2[ 0]='c'，不同 → dp[ 1][ 1] = max(dp[ 0][ 1], dp[ 1][ 0 ]) = max(0,0) = 0 i=1, j=2: 'a' vs 'a'，相同 → dp[ 1][ 2] = dp[ 0][ 1 ] + 1 = 0 + 1 = 1 i=1, j=3: 'a' vs 'b'，不同 → dp[ 1][ 3] = max(dp[ 0][ 3], dp[ 1][ 2 ]) = max(0,1) = 1 i=2, j=1: 'b' vs 'c'，不同 → dp[ 2][ 1] = max(dp[ 1][ 1], dp[ 2][ 0 ]) = max(0,0) = 0 i=2, j=2: 'b' vs 'a'，不同 → dp[ 2][ 2] = max(dp[ 1][ 2], dp[ 2][ 1 ]) = max(1,0) = 1 i=2, j=3: 'b' vs 'b'，相同 → dp[ 2][ 3] = dp[ 1][ 2 ] + 1 = 1 + 1 = 2 i=3, j=1: 'a' vs 'c'，不同 → dp[ 3][ 1] = max(dp[ 2][ 1], dp[ 3][ 0 ]) = max(0,0) = 0 i=3, j=2: 'a' vs 'a'，相同 → dp[ 3][ 2] = dp[ 2][ 1 ] + 1 = 0 + 1 = 1 i=3, j=3: 'a' vs 'b'，不同 → dp[ 3][ 3] = max(dp[ 2][ 3], dp[ 3][ 2 ]) = max(2,1) = 2 i=4, j=1: 'c' vs 'c'，相同 → dp[ 4][ 1] = dp[ 3][ 0 ] + 1 = 0 + 1 = 1 i=4, j=2: 'c' vs 'a'，不同 → dp[ 4][ 2] = max(dp[ 3][ 2], dp[ 4][ 1 ]) = max(1,1) = 1 i=4, j=3: 'c' vs 'b'，不同 → dp[ 4][ 3] = max(dp[ 3][ 3], dp[ 4][ 2 ]) = max(2,1) = 2 最终 dp[ 4][ 3 ] = 2，即 LCS 长度为 2（对应 LCS 可以是 "ab" 或 "ac"）。步骤2：计算 SCS 长度 SCS 长度 = m + n - lcs_ len = 4 + 3 - 2 = 5。与示例一致。算法复杂度时间复杂度：O(m * n)，用于填 dp 表。空间复杂度：可以优化为 O(min(m, n))，因为 dp 递推只需要上一行和当前行。扩展如果题目要求输出一个具体的最短公共超序列（而不仅仅是长度），可以在得到 dp 表后通过回溯构造。方法是从 dp[ m][ n ] 开始，根据状态转移反向追踪：若当前位置字符相同，则将该字符加入结果，并移至左上角 (i-1, j-1)。否则，选择 dp 值较大的方向移动，并将对应字符串的当前字符加入结果（因为超序列需要包含该字符）。最终将结果字符串反转即可。这就是“最短公共超序列长度”问题的完整求解思路，核心在于利用 LCS 来避免重复计算公共部分。