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

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        vector<vector<int>> dp(n+1,vector<int> (m+1,0));
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        string str;
        for(int i = n,j = m;dp[i][j] >= 1;){
            if(s1[i-1] == s2[j-1]){
                str += s1[i-1];
                i--;
                j--;
            }
            else if(dp[i-1][j] >= dp[i][j-1]){
                i--;
            }
            else{
                j--;
            }
        }
        reverse(str.begin(), str.end());
        return str == "" ? "-1":str;
    }
};