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

#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) {
        // write code here
        int m = s1.size(), n = s2.size();
        if (m == 0 || n == 0) return "-1";
        vector<vector<int>> f(m + 1, vector<int> (n + 1, 0));
        int maxLength = 0, pos = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i][j - 1], f[i - 1][j]);
                }
            }
        }
        if (f[m][n] == 0) return "-1";
        /* 2. 回溯还原字符串 */
        string lcs;
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1[i - 1] == s2[j - 1]) {          // 公共字符
                lcs.push_back(s1[i - 1]);
                --i;
                --j;
            } else if (f[i - 1][j] >= f[i][j - 1])
                --i;                              // 向上走
            else
                --j;                              // 向左走
        }
        reverse(lcs.begin(), lcs.end());          // 回溯是倒序
        return lcs;
    }
};