动态规划方法:
首先使用二维数组dp,确定其元素dp[i][j]的含义(此处指str1的第i个元素和str2的第j个元素为结尾的最长公共子串长度,注意最后一个元素必然是相同的)。
然后找到状态转移方程:若新加入元素相同,则在原长度加一,即dp[i][j]=dp[i-1][j-1]+1,否则为0。接着考虑dp数组的初始化即边界条件。
最后由于要返回最长公共子串序列,而dp数组只记录了其长度数值,故需要确定最大长度,即dp数组最大值,以及公共子串的结尾标志,通过结尾标志和子串长度回到原字符串中寻找公共子串。
class Solution { public: /** * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ string LCS(string str1, string str2) { // write code here //使用二维数组 /* int maxLen=0; int maxLastind=0; int dp[str1.length()][str2.length()]; dp[0][0]=0;//初始化 for(int i=0;i<str1.length();++i) { for(int j=0;j<str2.length();++j) { if(str1[i]==str2[j]) { if(i==0 || j==0) {//边界条件 dp[i][j]=1; } else {//状态转移方程 dp[i][j]=dp[i-1][j-1]+1; if(dp[i][j]>maxLen) {//确定最长公共子串的长度与结束标志 maxLen=dp[i][j]; maxLastind=i; } } } else dp[i][j]=0; } } return str1.substr(maxLastind-maxLen+1,maxLen); */ //优化:使用一维数组 int maxLen=0; int maxLastind=0; vector<int> dp(str2.length(),0); for(int i=0;i<str1.length();++i) { for(int j=str2.length()-1;j>=0;--j) {//注意必须是倒序,因为原本需要用到左上角元素值,故从右往左进行 if(str1[i]==str2[j]) { if(i==0 || j==0) { dp[j]=1; } else { dp[j]=dp[j-1]+1; if(dp[j]>maxLen) { maxLen=dp[j]; maxLastind=j; } } } else dp[j]=0; } } return str2.substr(maxLastind-maxLen+1,maxLen); } };