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

最长公共子串

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

相关推荐

不愿透露姓名的神秘牛友
06-26 14:50
人力小鱼姐:有后面墨迹那两句的时间问题早回答完了
点赞 评论 收藏
分享
白火同学:大二有这水平很牛了,可以适当对关键信息加粗一点,比如关键技术、性能指标之类的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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