重庆市建设信息网站,网站建设的公司价格,引流推广公司,seo短期培训班最长公共子序列#xff1a;
如果要回溯出整个字符串的答案的话#xff0c;可以直接看dp[i][len2-1]列#xff0c;或者dp[len1-1][i]这一行#xff0c;变化的时候#xff0c;则代表要选这个字符#xff0c;然后连起来就可以了。#xff08;即构造字符串的过程是On的
如果要回溯出整个字符串的答案的话可以直接看dp[i][len2-1]列或者dp[len1-1][i]这一行变化的时候则代表要选这个字符然后连起来就可以了。即构造字符串的过程是On的
class Solution {
public:/*** longest common substring* param str1 string字符串 the string* param str2 string字符串 the string* return string字符串*/int dp[5005][5005];string LCS(string str1, string str2) {// write code hereint len1 str1.size();int len2 str2.size();for(int i 0; ilen1; i) dp[i][0] (str1[i] str2[0])?1:dp[i-1][0];for(int i 0; ilen2; i) dp[0][i] (str1[0] str2[i])?1:dp[0][i-1];for(int i 1; ilen1; i) {for(int j 1; jlen2; j) {if(str1[i] str2[j]) dp[i][j] dp[i-1][j-1] 1;else dp[i][j] max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1]));}}for(int i 0; ilen1; i) {for(int j 0; jlen2; j) {cout dp[i][j] ;}cout endl;}cout dp[len1-1][len2-1] endl;return str1;}
};
最长公共子串
class Solution {
public:/*** longest common substring* param str1 string字符串 the string* param str2 string字符串 the string* return string字符串*/int dp[5005][5005];string LCS(string str1, string str2) {// write code hereint len1 str1.size();int len2 str2.size();for(int i 0; ilen1; i) dp[i][0] (str1[i] str2[0])?1:0;for(int i 0; ilen2; i) dp[0][i] (str1[0] str2[i])?1:0;for(int i 1; ilen1; i) {for(int j 1; jlen2; j) {if(str1[i] str2[j]) dp[i][j] dp[i-1][j-1] 1;else dp[i][j] 0;}}int mx 0;string ans;for(int i 0; ilen1; i) {for(int j 0; jlen2; j) {if(dp[i][j] mx) {mx dp[i][j];ans str1.substr(i-mx1, mx);}}}return ans;}
};
