5.最长回文子串

解法：动态规划

思路：

dp[i] [j]表示i到j子串是否为回文串，L表示子串长度

L=1时，i==j时全为回文串

L=2时，j=i+1，s[i]=s[j]时是回文串

L>2时，枚举L的长度（for），在同一个L下遍历左边界，j=i+L-1

dp[i] [j] = dp[i+1] [j-1] && ( s[i] == s[j] )

代码：

class Solution {
public:string longestPalindrome(string s) {int n=s.size();int maxL=1;vector<vector<int>> dp(n,vector<int>(n));int begin=0;int end=0;//L=1的全为回文for(int i=0;i<n;i++){dp[i][i]=1;}for(int L=2;L<=n;L++){for(int i=0;i<n;i++){int j=i+L-1;if(j>=n) break;//首尾相等时才继续验证回文串if(s[i]==s[j]){//长度为2时两字符相等即为回文串if(L==2){dp[i][j]=1; }else if(dp[i+1][j-1]==1){ //长度>2时 除掉头尾是回文才是回文串dp[i][j]=1;}else{dp[i][j]=0;}}else{dp[i][j]=0;}//更新最大长度，记录子串起点if(dp[i][j]==1 && L>maxL){begin=i;maxL=L;}}}return  s.substr(begin, maxL);}
};