题解 | 最长公共子序列(二)

1、解题思路

1. 动态规划：定义 dp[i][j] 为 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。递推关系： 如果 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])。初始条件：dp[0][j] = 0 和 dp[i][0] = 0（表示空字符串的 LCS 长度为 0）。
2. 反向构造 LCS：从 dp[m][n] 开始，反向追踪 dp 表格，构造出 LCS。如果 str1[i-1] == str2[j-1]，则该字符属于 LCS，然后移动到 dp[i-1][j-1]。否则，移动到 dp[i-1][j] 或 dp[i][j-1] 中的较大值方向。
3. 边界条件：如果 dp[m][n] == 0，返回 "-1"。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.size(), n = s2.size();
        if (m == 0 || n == 0) {
            return "-1";
        }

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        if (dp[m][n] == 0) {
            return "-1";
        }

        string res;
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1[i - 1] == s2[j - 1]) {
                res.push_back(s1[i - 1]);
                --i;
                --j;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                --i;
            } else {
                --j;
            }
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        int m = s1.length(), n = s2.length();
        if (m == 0 || n == 0) return "-1";
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        if (dp[m][n] == 0) return "-1";
        StringBuilder res = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                res.append(s1.charAt(i - 1));
                --i;
                --j;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                --i;
            } else {
                --j;
            }
        }
        return res.reverse().toString();
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self, s1: str, s2: str) -> str:
        # write code here
        m, n = len(s1), len(s2)
        if m == 0 or n == 0:
            return "-1"
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if dp[m][n] == 0:
            return "-1"
        res = []
        i, j = m, n
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                res.append(s1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
        res.reverse()
        return "".join(res)

3、复杂度分析

• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)（满足题目要求的 O(n²)）