子序列要连续,看样例是这样的。
测试数据有问题
看如下样例,答案应该是-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);
}
};
京公网安备 11010502036488号