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

学习了

#include <string>
#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) {
        if (s1.size()*s2.size() == 0)return "-1";
        vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1,
                                0)); // 记录最小值
        vector<vector<pair<int, int> > > pre(
            s1.size() + 1, vector<pair<int, int>>(s2.size() + 1, make_pair(0,
                    0))); // 记录最小值来源
        for (int i = 0; i < s1.size(); i++) {
            for (int j = 0; j < s2.size(); j++) {
                if (s1[i] == s2[j]) { // 相等时
                    if (dp[i][j] + 1 > dp[i + 1][j + 1]) { // 有更长的值
                        dp[i + 1][j + 1] = dp[i][j] + 1; // 长度
                        pre[i + 1][j + 1] = {i, j}; // 来源
                    }
                } else {
                    if (dp[i + 1][j] > dp[i + 1][j + 1]) { // 不匹配s2
                        dp[i + 1][j + 1] = dp[i + 1][j]; // 长度
                        pre[i + 1][j + 1] = {i + 1, j}; // 来源
                    }
                    if (dp[i][j + 1] > dp[i + 1][j + 1]) { // 不匹配s1
                        dp[i + 1][j + 1] = dp[i][j + 1]; // 长度
                        pre[i + 1][j + 1] = {i, j + 1}; // 来源
                    }
                }
            }
        }
        if (dp[s1.size()][s2.size()] == 0)return "-1"; // 长度为0
        string res = "";
        int i = s1.size();
        int j = s2.size();
        while (i != 0 && j != 0) { // 重构字符串
            if (s1[i - 1] == s2[j - 1]) res = s1[i - 1] + res; // 相等的位置
            auto [pi, pj] = pre[i][j]; // 上一个i,j
            i = pi;
            j = pj;
        }
        return res;
    }
};