最长公共子序列的变种：带限制的最长公共子序列

字数 2174 2025-10-28 11:34:06

最长公共子序列的变种：带限制的最长公共子序列

题目描述
给定三个字符串 s1, s2 和 s3，找出 s1 和 s2 的最长公共子序列，且这个子序列必须包含 s3 作为其子序列。如果不存在这样的公共子序列，则返回 0。

解题过程

这个问题是标准最长公共子序列（LCS）的扩展，增加了一个约束条件：找到的 LCS 必须包含第三个字符串 s3 作为其子序列。这意味着我们需要在 s1 和 s2 的公共子序列中，寻找那些“包裹”着 s3 的子序列，并取其中最长的。

我们可以将问题分解为两个阶段：

在 s1 和 s2 中共同匹配出完整的 s3。
在匹配 s3 的各个部分之间，插入 s1 和 s2 的公共子序列（这些部分与 s3 无关），使得整个序列最长。

步骤 1：定义状态

我们使用一个三维动态规划数组 dp。

dp[i][j][k] 表示考虑字符串 s1 的前 i 个字符、s2 的前 j 个字符，并且已经匹配了 s3 的前 k 个字符时，所能得到的最长满足条件的公共子序列的长度。
i 的范围是 [0, len(s1)]，j 的范围是 [0, len(s2)]，k 的范围是 [0, len(s3)]。
我们的目标是 dp[len(s1)][len(s2)][len(s3)]。

步骤 2：状态转移方程

状态转移需要考虑当前我们如何处理 s1[i-1], s2[j-1] 和 s3[k-1]（注意字符串索引从0开始，dp索引从1开始对应）。

情况 1：s1 的第 i 个字符和 s2 的第 j 个字符相等。
这是最核心的情况，我们继续细分：
a) 如果我们当前正在匹配 s3（即 k > 0），并且 s1[i-1] (等于 s2[j-1]) 也等于 s3[k-1]。
那么，这个字符既可以用来继续匹配 s3，也可以不作为匹配 s3 的一部分，而是作为插入在 s3 匹配间隙的普通 LCS 字符。
* 用于匹配 s3：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + 1)。这表示我们成功匹配了 s3 的一个新字符，长度加1。
* 用于普通 LCS：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1)。这表示这个字符只是用来延长我们当前的公共子序列，不参与对 s3 的匹配。

b) 如果 s1[i-1] 等于 s2[j-1]，但不等于 s3[k-1]（或者 k 已经达到 len(s3)，无需再匹配）。
    那么这个字符只能作为**普通 LCS 字符**，用于填充 s3 匹配完成后的部分，或者填充在 s3 的匹配间隙中。
    `dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1)`。

情况 2：s1 的第 i 个字符和 s2 的第 j 个字符不相等。
那么这两个字符不可能同时出现在公共子序列中。我们有两个选择：
* 忽略 s1[i-1]：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k])
* 忽略 s2[j-1]：dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])

步骤 3：初始化
dp[0][j][0] = 0：s1 为空字符串时，只要还没开始匹配 s3 (k=0)，最长公共子序列长度就是 0。
dp[i][0][0] = 0：s2 为空字符串时，同理。
dp[0][j][k] = -INF (k > 0)：如果 s1 是空的，但我们却要求匹配 s3 的一部分 (k>0)，这是不可能的，初始化为一个极小的值（例如负无穷）。
dp[i][0][k] = -INF (k > 0)：同理，s2 为空时不可能匹配非空的 s3。

步骤 4：计算顺序
我们使用三重循环，依次递增地计算 i, j, k。因为 dp[i][j][k] 依赖于 dp[i-1][j-1][k-1]，dp[i-1][j-1][k]，dp[i-1][j][k] 和 dp[i][j-1][k]，所以按照从小到大的顺序遍历即可。

步骤 5：最终结果
最终答案存储在 dp[len(s1)][len(s2)][len(s3)] 中。
但是，如果这个值小于 0（或者小于 len(s3)），说明我们无法找到一个包含完整 s3 作为子序列的 s1 和 s2 的公共子序列。根据题目要求，如果不存在，返回 0。否则返回该值。

举例说明
假设 s1 = "abcde", s2 = "ace", s3 = "ce"。
我们想找 s1 和 s2 的 LCS（比如 "ace"），并且这个 LCS 必须包含 "ce" 作为子序列。

dp 表计算过程（简化表示）：
最终，dp[5][3][2] 会这样计算：我们先用 s1 的 'c' 匹配 s3 的 'c'（k 从 0->1），然后用 s1 的 'e' 匹配 s3 的 'e'（k 从 1->2）。在匹配 'c' 之前，我们可以插入 s1 和 s2 的公共字符 'a'。所以最终序列是 "a" + "c" + "e" = "ace"，长度为 3。

如果 s3 无法被完整匹配，比如 s3 = "cf"，那么最终 dp[5][3][2] 将会是一个无效值（初始的负无穷），我们返回 0。

这个算法通过三维 DP 表，清晰地刻画了在匹配 s3 的约束下，构建 s1 和 s2 最长公共子序列的过程。

最长公共子序列的变种：带限制的最长公共子序列题目描述给定三个字符串 s1, s2 和 s3，找出 s1 和 s2 的最长公共子序列，且这个子序列必须包含 s3 作为其子序列。如果不存在这样的公共子序列，则返回 0。解题过程这个问题是标准最长公共子序列（LCS）的扩展，增加了一个约束条件：找到的 LCS 必须包含第三个字符串 s3 作为其子序列。这意味着我们需要在 s1 和 s2 的公共子序列中，寻找那些“包裹”着 s3 的子序列，并取其中最长的。我们可以将问题分解为两个阶段：在 s1 和 s2 中共同匹配出完整的 s3。在匹配 s3 的各个部分之间，插入 s1 和 s2 的公共子序列（这些部分与 s3 无关），使得整个序列最长。步骤 1：定义状态我们使用一个三维动态规划数组 dp 。 dp[i][j][k] 表示考虑字符串 s1 的前 i 个字符、s2 的前 j 个字符，并且已经匹配了 s3 的前 k 个字符时，所能得到的最长满足条件的公共子序列的长度。 i 的范围是 [ 0, len(s1)]， j 的范围是 [ 0, len(s2)]， k 的范围是 [ 0, len(s3) ]。我们的目标是 dp[len(s1)][len(s2)][len(s3)] 。步骤 2：状态转移方程状态转移需要考虑当前我们如何处理 s1[ i-1], s2[ j-1] 和 s3[ k-1 ]（注意字符串索引从0开始，dp索引从1开始对应）。情况 1：s1 的第 i 个字符和 s2 的第 j 个字符相等。这是最核心的情况，我们继续细分： a) 如果我们当前正在匹配 s3（即 k > 0），并且 s1[ i-1] (等于 s2[ j-1]) 也等于 s3[ k-1 ]。那么，这个字符既可以用来继续匹配 s3 ，也可以不作为匹配 s3 的一部分，而是作为插入在 s3 匹配间隙的普通 LCS 字符。 * 用于匹配 s3 ： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + 1) 。这表示我们成功匹配了 s3 的一个新字符，长度加1。 * 用于普通 LCS ： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1) 。这表示这个字符只是用来延长我们当前的公共子序列，不参与对 s3 的匹配。情况 2：s1 的第 i 个字符和 s2 的第 j 个字符不相等。那么这两个字符不可能同时出现在公共子序列中。我们有两个选择： * 忽略 s1[ i-1]： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) * 忽略 s2[ j-1]： dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]) 步骤 3：初始化 dp[0][j][0] = 0 ：s1 为空字符串时，只要还没开始匹配 s3 (k=0)，最长公共子序列长度就是 0。 dp[i][0][0] = 0 ：s2 为空字符串时，同理。 dp[0][j][k] = -INF (k > 0)：如果 s1 是空的，但我们却要求匹配 s3 的一部分 (k>0)，这是不可能的，初始化为一个极小的值（例如负无穷）。 dp[i][0][k] = -INF (k > 0)：同理，s2 为空时不可能匹配非空的 s3。步骤 4：计算顺序我们使用三重循环，依次递增地计算 i, j, k。因为 dp[i][j][k] 依赖于 dp[i-1][j-1][k-1] ， dp[i-1][j-1][k] ， dp[i-1][j][k] 和 dp[i][j-1][k] ，所以按照从小到大的顺序遍历即可。步骤 5：最终结果最终答案存储在 dp[len(s1)][len(s2)][len(s3)] 中。但是，如果这个值小于 0（或者小于 len(s3)），说明我们无法找到一个包含完整 s3 作为子序列的 s1 和 s2 的公共子序列。根据题目要求，如果不存在，返回 0。否则返回该值。举例说明假设 s1 = "abcde", s2 = "ace", s3 = "ce"。我们想找 s1 和 s2 的 LCS（比如 "ace"），并且这个 LCS 必须包含 "ce" 作为子序列。 dp 表计算过程（简化表示）：最终， dp[5][3][2] 会这样计算：我们先用 s1 的 'c' 匹配 s3 的 'c'（k 从 0->1），然后用 s1 的 'e' 匹配 s3 的 'e'（k 从 1->2）。在匹配 'c' 之前，我们可以插入 s1 和 s2 的公共字符 'a'。所以最终序列是 "a" + "c" + "e" = "ace"，长度为 3。如果 s3 无法被完整匹配，比如 s3 = "cf"，那么最终 dp[5][3][2] 将会是一个无效值（初始的负无穷），我们返回 0。这个算法通过三维 DP 表，清晰地刻画了在匹配 s3 的约束下，构建 s1 和 s2 最长公共子序列的过程。