题意整理

本题题意既找到给定的两个字符串中的最长公共子序列，子序列为一个序列去除部分（也可以不去除）元素后，其他元素相对位置保持不变得到的序列。

方法一：动态规划

核心思想：

分析题意可以知道可以通过二维动态规划解决这道题
假设两个字符串的长度分别为 。建立一个大小为行，列的dp数组，其中表示 长度为 的前缀和 长度为 的前缀两个字符串的最长公共子序列的长度。故有当 或 时值为。
对其他情况，当 时，可将这两个字符作为公共字符，故此时
当 时,应取 和 中较大的一项进行转移

为了得到答案，同时需要一个方向数组记录转移方向，最后进行判断
图示：

核心代码：

class Solution {
public:
    string LCS(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        if(m == 0 || n == 0) {
            return "-1";//某个字符串长度为0，公共子序列必不存在
        }
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        vector<vector<char>> turn(m, vector<char>(n, 0));
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                //按情况进行转移
                if(s1[i] == s2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    if(dp[i][j + 1] > dp[i + 1][j]) {
                        dp[i + 1][j + 1] = dp[i][j + 1];
                        turn[i][j] = 'U';//来自上方
                    } else {
                        dp[i + 1][j + 1] = dp[i + 1][j];
                        turn[i][j] = 'L';//来自左侧
                    }
                }
            }
        }
        if(dp[m][n] == 0) {
            return "-1";
        }
        string ans;
        //从结尾开始寻找
        for (int i = m - 1, j = n - 1; i >= 0 && j >= 0;) {
            if (turn[i][j] == 'U') --i;//往上方转移
            else if (turn[i][j] == 'L') --j;//往左侧转移
            else {//找到一个公共字符，进行记录
                ans += s1[i];
                --i, --j;
            }
        }
        reverse(ans.begin(), ans.end());//因为是倒序寻找，需要进行翻转
        return ans;
    }
};

复杂度分析：

时间复杂度：,其中 分别为两个字符串的长度。因为二维数组有 行和列，需要对每个元素进行计算
空间复杂度：,即为数组以及方向数组的的开销

方法二：空间优化的答案查找

核心思想：

方法一中为了得到最后的子序列，使用了一个二维矩阵记录状态转移的方向，实际上可以直接使用dp数组与相邻值的差异直接进行判断，省去记录方向的数组的开销。
寻找答案思路：从后往前找，当时说明找到了一个字母， 和 都执行前进，否则选择dp值较大的方向前进

核心代码：

class Solution {
public:
    string LCS(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        if(m == 0 || n == 0) {
            return "-1";//某个字符串长度为0，公共子序列必不存在
        }
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                //按情况进行转移
                dp[i + 1][j + 1] = s1[i] == s2[j] ? dp[i][j] + 1 : max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
        if(dp[m][n] == 0) {
            return "-1";
        }
        string res;
        //从结尾开始寻找
        m -= 1;
        n -= 1;
        for(; m >= 0; ) {
            //倒序寻找子序列
            if(s1[m] == s2[n]) {
                //找到了符合的
                res += s1[m];
                m -=1;
                n -=1;
            } else if(dp[m + 1][n] > dp[m][n + 1]) {
                n -= 1;
            } else {
                m -=1;
            }
        }
        reverse(res.begin(), res.end());//因为是倒序寻找，需要进行翻转
        return res;
    }
};

复杂度分析：

时间复杂度：,其中 分别为两个字符串的长度。因为二维数组有 行和 列，需要对每个元素进行计算
空间复杂度：,即为数组的开销