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