描述

给定两个字符串 $str1$ 和 $str2$，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列.

数据范围：$0≤∣str1∣,∣str2∣≤2000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

示例1
输入：

"1A2C3D4B56","B1D23A456A"

返回值：

"123456"

示例2
输入：

"abc","def"

返回值：

"-1"

示例3
输入：

"abc","abc"

返回值：

"abc"

示例4
输入：

"ab",""

返回值：

"-1"

题解

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        string res = "";
        int n = s1.size(), m = s2.size();
        vector<vector<int>> f(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]) f[i][j] = f[i-1][j-1] + 1;
                else f[i][j] = max(f[i-1][j], f[i][j-1]);
            }
        }
        int n1 = n, m1 = m;
        while(n1 && m1) {
            if(s1[n1-1] == s2[m1-1]) {
                res += s1[n1-1];
                n1--; m1--;
            }else {
                if(f[n1-1][m1] > f[n1][m1-1]) {
                    n1--;
                }else m1--;
            }
        }
        if(res.size() == 0) return "-1";
        reverse(res.begin(), res.end());
        return res;
    }
};