子序列要连续,看样例是这样的。

测试数据有问题
看如下样例,答案应该是-1.
图片说明

动态规划:

#define N 5001
int dp[N][N];
class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */

    int Get(int dp[N][N], int i, int j){
        if(i < 0 || j < 0){
            return 0;
        }
        return dp[i][j];
    }
    string LCS(string str1, string str2) {
        // write code here   
        memset(dp, 0, sizeof(int)*N*N);
        int maxi = -1, maxj = -1;
        for(int i = 0; i < str1.size(); i++){
            for(int j = 0; j < str2.size(); j++){
                if(str1[i] == str2[j]){
                    dp[i][j] = Get(dp, i-1,j-1)+1;
                     if(maxi == -1 || maxj == -1 || dp[i][j] > dp[maxi][maxj]){
                        maxi = i;
                        maxj = j;
                    }
                }
            }
        }
        if(maxi == -1 || maxj == -1){
            return "-1";
        }
        int n = dp[maxi][maxj];
        return str1.substr(maxi-n+1, n);                   
    }
};