题解 | #最长公共子序列-II#

class Solution {
private:
    string build(string& str, int i, int j, vector<vector<int>>& directions){
        if(i < 1 || j < 1){
            return "";
        }
        string ans;
        if(directions[i][j] == 1){
            // 来自左上方
            ans += build(str, i - 1, j - 1, directions);
            ans += str[i-1];
        }else if(directions[i][j] == 2){
            // 来自左侧
            ans = build(str, i, j - 1, directions);
        }else if(directions[i][j] == 3){
            // 来自右侧
            ans = build(str, i-1, j, directions);
        }
        return ans;
    }
public:
    string LCS(string s1, string s2) {
        // write code here
        int size1 = s1.size(), size2 = s2.size(), len = 0;
        vector<vector<int>> dp(size1+1, vector<int>(size2+1, 0)), directions(size1+1, vector<int>(size2+1, 0));
        for(int i = 1; i < size1 + 1; ++i){
            char e1 = s1[i-1];
            for(int j = 1; j < size2 + 1; ++j){
                char e2 = s2[j-1];
                // 左上方
                if(e1 == e2){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    directions[i][j] = 1;
                }else if(dp[i-1][j] < dp[i][j-1]){
                    dp[i][j] = dp[i][j-1];
                    // 左侧
                    directions[i][j] = 2;
                }else{
                    dp[i][j] = dp[i-1][j];
                    // 上方
                    directions[i][j] = 3;
                }
                len = max(len, dp[i][j]);
            }
        }
        if(!len){
            return "-1";
        }
        // 构造最长公共子序列
        return build(s1, size1, size2, directions);
    }
};