每日一题——最长公共子序列

视频讲解：B站视频
【[轻松掌握动态规划]5.最长公共子序列 LCS】 https://www.bilibili.com/video/BV1ey4y1d7oD/?share_source=copy_web&vd_source=b1f5728f3a9c87006fa48f39e09acbab
题解链接：最长公共子序列题解

题目描述

给定两个字符串 str1 和 str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回 "-1"。题目保证给出的数据仅会存在一个最长的公共子序列。

数据范围：
0 ≤ |str1|, |str2| ≤ 2000

要求：

• 空间复杂度：(O(n^2))
• 时间复杂度：(O(n^2))

示例

示例 1

输入：
"1A2C3D4B56", "B1D23A456A"
返回值：
"123456"

示例 2

输入：
"abc", "def"
返回值：
"-1"

示例 3

输入：
"abc", "abc"
返回值：
"abc"

示例 4

输入：
"ab", ""
返回值：
"-1"

解题思路

动态规划

最长公共子序列（LCS）问题是经典的动态规划问题。我们可以通过构建一个二维的动态规划表来解决。

动态规划表定义：

• 设 dp[i][j] 表示字符串 str1 的前 i 个字符和字符串 str2 的前 j 个字符的最长公共子序列的长度。

状态转移方程：

1. 如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
2. 如果 str1[i-1] != str2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

边界条件：

• 当 i == 0 或 j == 0 时，dp[i][j] = 0，因为空字符串与任何字符串的最长公共子序列长度为 0。

构建最长公共子序列：

• 从 dp[m][n] 开始回溯，根据 dp 表的值决定如何移动，最终构造出最长公共子序列。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 动态规划求最长公共子序列的长度
int LCSLength(const char* str1, const char* str2, int** dp, int len1, int len2) {
    // 遍历两个字符串的所有字符
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            // 如果当前字符匹配
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // LCS长度增加1
            } else {
                // 如果当前字符不匹配，取可能的最大LCS长度
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    return dp[len1][len2]; // 返回最长公共子序列的长度
}

// 根据 dp 数组回溯构建最长公共子序列
void buildLCS(const char* str1, const char* str2, int** dp, int len1, int len2, char* lcs, int lcsLength) {
    // 从LCS的最后一个字符开始填充
    lcs[lcsLength--] = '\0'; // 添加字符串结束符

    // 从dp数组的最后一个元素开始回溯
    for (int i = len1, j = len2; i > 0 && j > 0;) {
        // 如果当前字符匹配，则该字符是LCS的一部分
        if (str1[i - 1] == str2[j - 1]) {
            lcs[lcsLength--] = str1[i - 1]; // 将字符加入LCS
            i--;
            j--;
        }
        // 如果当前字符不匹配，则选择LCS长度较大的方向继续回溯
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--; // 向上移动
        } else {
            j--; // 向左移动
        }
    }
}

// 主函数，计算最长公共子序列
char* LCS(const char* str1, const char* str2) {
    int len1 = strlen(str1); // 获取str1的长度
    int len2 = strlen(str2); // 获取str2的长度

    // 分配dp数组
    int** dp = (int**)calloc(len1 + 1, sizeof(int*));
    for (int i = 0; i < len1 + 1; i++) {
        dp[i] = (int*)calloc(len2 + 1, sizeof(int));
    }

    // 计算最长公共子序列的长度
    int lcsLength = LCSLength(str1, str2, dp, len1, len2);

    // 如果LCS长度为0，返回"-1"
    if (lcsLength == 0) {
        for (int i = 0; i <= len1; i++) {
            free(dp[i]);
        }
        free(dp);
        return "-1";
    }

    // 分配LCS字符串空间
    char* lcs = (char*)malloc((lcsLength + 1) * sizeof(char));

    // 根据dp数组构建LCS
    buildLCS(str1, str2, dp, len1, len2, lcs, lcsLength);

    // 释放dp数组
    for (int i = 0; i <= len1; i++) {
        free(dp[i]);
    }
    free(dp);

    return lcs; // 返回构建的LCS字符串
}

代码解析

1. 动态规划表初始化：

   • 使用二维数组 dp 存储子问题的解，dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。

2. 填充 dp 表：

   • 遍历 str1 和 str2，根据字符是否相等更新 dp 表的值。

3. 回溯构造 LCS：

   • 从 dp[m][n] 开始，根据 dp 表的值决定向左、向上或向左上移动，逐步构造最长公共子序列。

4. 返回结果：

   • 如果最长公共子序列长度为 0，返回 "-1"；否则返回构造的 LCS。

复杂度分析

• 时间复杂度：

  • 填充 dp 表需要 (O(m \times n)) 的时间。
  • 回溯构造 LCS 需要 (O(m + n)) 的时间。
  • 总时间复杂度为 (O(m \times n))。

• 空间复杂度：

  • 使用了一个二维数组 dp，空间复杂度为 (O(m \times n))。

图解分析

动态规划的详细过程解释

1. 状态转移图

状态转移图是动态规划的核心部分，它通过状态转移方程描述了如何通过已经解决的子问题推导出当前问题的解决方案。对于 最长公共子序列（LCS）问题，我们需要构建一个二维的 动态规划表（dp表），用来存储子问题的解，进而通过状态转移方程从小规模的子问题逐步解决到最终的大问题。

1.1 状态定义

在 LCS 问题中，dp[i][j] 表示字符串 str1 的前 i 个字符与字符串 str2 的前 j 个字符的 最长公共子序列的长度。

• dp[i][j] 是当前子问题的解。
• i 和 j 分别是两个字符串的字符索引。

1.2 状态转移方程

• 字符匹配：

  • 如果 str1[i-1] == str2[j-1]，说明当前字符是 LCS 的一部分。
  • 因此，dp[i][j] = dp[i-1][j-1] + 1。
  • 这意味着我们将当前字符加入到已有的公共子序列中，公共子序列的长度比之前多了一个字符。

• 字符不匹配：

  • 如果 str1[i-1] != str2[j-1]，说明当前字符不是 LCS 的一部分。
  • 因此，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
  • 这里我们选择 dp[i-1][j] 和 dp[i][j-1] 中的较大值，表示不匹配的情况下我们要么从 str1 中删除一个字符，要么从 str2 中删除一个字符。

2. 回溯路径

回溯路径是从 dp[m][n] 开始，通过回溯的方式追溯所有的公共字符，最终构建出 最长公共子序列。回溯的核心思想是从表格的右下角开始，逐步向左上角回溯，直到我们找到所有匹配的字符。

2.1 回溯过程

1. 从 dp[m][n] 开始：

   • m 和 n 分别是字符串 str1 和 str2 的长度。
   • dp[m][n] 存储了 str1 和 str2 的最终最长公共子序列的长度。

2. 沿着匹配字符的路径回溯：

   • 如果字符匹配（str1[i-1] == str2[j-1]），则说明该字符是 LCS 的一部分。

     • 将当前字符加入 LCS。
     • 向左上角移动，即 i-- 和 j--。

   • 如果字符不匹配（str1[i-1] != str2[j-1]），则我们选择 LCS 长度较大的方向继续回溯：

     • 如果 dp[i-1][j] > dp[i][j-1]，则向上移动，即 i--。
     • 否则，向左移动，即 j--。

3. 终止条件：

   • 当 i == 0 或 j == 0 时，回溯结束，此时我们已经找到整个 LCS。

2.2 回溯过程的具体步骤

假设我们有两个字符串：

• str1 = "ABCBDAB"
• str2 = "BDCAB"

我们构建 dp 表来存储子问题的解。

状态转移图（部分）：

• 从 dp[7][6] 开始：

  • str1[6] == str2[5]，字符 B 是 LCS 的一部分，加入 LCS，回溯到 dp[6][5]。
  • str1[5] == str2[4]，字符 A 是 LCS 的一部分，加入 LCS，回溯到 dp[5][4]。
  • str1[4] == str2[3]，字符 C 是 LCS 的一部分，加入 LCS，回溯到 dp[4][3]。
  • str1[3] == str2[2]，字符 B 是 LCS 的一部分，加入 LCS，回溯到 dp[3][2]。
  • str1[2] != str2[1]，选择 dp[2][1]，回溯到 dp[2][1]。
  • str1[1] == str2[1]，字符 B 是 LCS 的一部分，加入 LCS，回溯到 dp[1][0]。

• 最终构造出的 LCS 为：BCAB

3. 图示解释

为了帮助理解，假设我们已经构建了状态转移图 dp，并开始回溯：

• 图中的矩阵表示每一对 (i, j) 位置的 LCS 长度。
• 从右下角 dp[7][6] 开始，我们根据字符是否匹配来决定回溯的方向。
• 如果匹配，则将字符添加到 LCS 中，并向左上方移动。
• 如果不匹配，选择较大值的方向继续回溯，直到到达矩阵的上方或左方边界。

总结

• 最长公共子序列问题是动态规划的经典应用。
• 通过构建 dp 表和回溯法，可以高效地解决问题。
• 在实际应用中，需要注意边界条件和特殊情况的处理（如空字符串）。