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

最长公共子串

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

相关推荐

10-02 19:29
已编辑
浙江科技大学 运营
点赞 评论 收藏
分享
Java面试先知:我也是和你一样的情况,hr 说等开奖就行了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务