最长连续公共子序列?测试数据有误吧

最长公共子串

http://www.nowcoder.com/questionTerminal/f33f5adc55f444baa0e0ca87ad8a6aac

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

测试数据有问题
看如下样例,答案应该是-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);                   
    }
};
全部评论
因为你自己修改了测试输入但是没修改测试输出啊emmmm
点赞 回复 分享
发布于 2020-11-18 19:05

相关推荐

11-02 08:15
已编辑
门头沟学院 Java
美团 Java后端开发 10w刀 美硕
YamadaAnna:包留美的,你拿的美团 招银,没一个不加班的。考虑一下未来吧,应届生的工资真不重要,10w刀税后6w,省省还是能活下去的。回国了35岁怎么办,难道35岁还能返美么,就算35岁还能在国内找到工作,难道打算一辈子9点10点下班么。你有能力在美利坚找到工作,回国如果不是哪个965大厂给你发个ssp,真不值得。 等抽不中h1b,没办法了再回国吧。
点赞 评论 收藏
分享
09-13 09:44
门头沟学院 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务