题解 | #NC92_LCS最长公共子序列#

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
        // 构造最大公共子序列长度矩阵
        vector<vector<int>> maxLen(s1.size()+1, vector<int>(s2.size()+1, 0)); // 大一圈，方便计算边界
        for(int i = 1; i <= s1.size(); i++)
            for (int j = 1; j <= s2.size(); j++) {
                if (s1[i - 1] == s2[j - 1])
                    maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
                else if (s1[i - 1] != s2[j - 1])
                    maxLen[i][j] = max(maxLen[i-1][j], maxLen[i][j-1]);
            }
        string res;
        int i = s1.size();
        int j = s2.size();
        while (maxLen[i][j]) {
            if (s1[i - 1] == s2[j - 1]) {
                res.append(s1.substr(i - 1, 1));
                i--;
                j--;
            }
            else {
                maxLen[i - 1][j] >= maxLen[i][j - 1] ? i-- : j--; // >=保证构造顺序固定
                // 元素不相等但最大公共子序列长度相等时优先向上
            }
        }
        reverse(res.begin(), res.end());
        if(!res.empty())
            return res;
        return "-1";
    }
};