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

class Solution {
  public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    /*
	  注解：子序列不需要连续，子串需要连续。
	  1、求最长公共子序列长度 dp[i][j]：表示：s1[1-i]的子序列，s2[1-j]的子序列 的最长公共数
	  2、我们在dp求最长公共数时，用一个数组PII pre[i][j] 存储当前状态[i,j]是由那个位置转移的
	  3、最后，我们从最后m-1,n-1倒叙开始找到公共子序列，直到i=0||j=0，
	  4、返回reverse(s.begin(),s.end());
	*/
    string LCS(string s1, string s2) {
        // write code here
        s1 = " " + s1, s2 = " " + s2;
        int m = s1.size(), n = s2.size();
        //dp[i][j] 表示s1[i]前i个子序列和s2[j]的前j个子序列的最长公共
        vector<vector<int>>dp(m, vector<int>(n, 0));
        string s = "";
        vector<vector<pair<int, int>>>pre(m, vector<pair<int, int>>(n, {0, 0}));
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    pre[i][j] = {i - 1, j - 1};
                } else {
                    if (dp[i - 1][j] > dp[i][j - 1]) {
                        pre[i][j] = {i - 1, j};
                    } else {
                        pre[i][j] = {i, j - 1};
                    }
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        if (!dp[m - 1][n - 1]) return "-1";
        int i = m - 1, j = n - 1;
        while (i != 0 && j != 0) {
            if (s1[i] == s2[j]) {
                s += s1[i];
            }
            auto [pi, pj] = pre[i][j];
            i = pi,j = pj;
        }
        reverse(s.begin(),s.end());
        return s;
    }
   

};