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

#include <utility>
#include <vector>
class Solution {
public:
    string x, y;

    string getPath(int i, int j, vector<vector<int>>& d) {
        string res;
        if (i == 0 || j == 0) return res;
        if (d[i][j] == 1) {
            res += getPath(i - 1, j - 1, d);
            res += x[i - 1];
        } else if (d[i][j] == 2) {
            res += getPath(i - 1, j, d);
        } else if (d[i][j] == 3) {
            res += getPath(i, j - 1, d);
        }
        return res;
    }

    string LCS(string s1, string s2) {
        if (s1.length() == 0 || s2.length() == 0) return "-1";
        int n = s1.size(), m = s2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        vector<vector<int>> d(n + 1, vector<int>(m + 1, 0));
        x = s1;
        y = s2;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    d[i][j] = 1;  // 来自左上方
                } else {
                    if (f[i - 1][j] > f[i][j - 1]) {
                        f[i][j] = f[i - 1][j];
                        d[i][j] = 2;  // 来自上方
                    } else {
                        f[i][j] = f[i][j - 1];
                        d[i][j] = 3; // 来自左方
                    }
                }
            }
        }

        string res = getPath(n, m, d);
        return res != "" ? res : "-1";
    }
};