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

方法：动态规划

主要分为以下两个步骤：

1、获取到两个字符串s1、s2在不同位置结尾的最长公共子序列长度，用一个二维数组dp将长度存储起来；

可以得到状态转移方程:

如果字符相等：dp[i][j] = 1 + dp[i - 1][j - 1];

如果字符不相等：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

2、从两个字符串的末尾向起点开始遍历，根据长度的大小来遍历，将得到的字符串进行反转即可得到最长的公共子序列。

时间复杂度：o(n²)

空间复杂度：o(n²)

class Solution {
  public:
    string LCS(string s1, string s2) {
        // 特殊情况处理
        if (s1.length() == 0 || s2.length() == 0)
            return "-1";

        int len1 = s1.length();
        int len2 = s2.length();
        // 存储在不同位置结尾的最长公共子序列长度
        vector<vector<int> > dp(len1 + 1, vector<int> (len2 + 1, 0));

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        string res = "";
        for (int i = len1, j = len2; dp[i][j] >= 1; ) {
            if (s1[i - 1] == s2[j - 1]) {
                res += s1[i - 1];
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1] ) {
                i--;
            } else {
                j--;
            }
        }
        reverse(res.begin(), res.end());
        // 最长公共子序列为空
        if (res.length() == 0)
            res = "-1";
        return res;
    }
};