[LeetCode]—Longest Palindromic Substring 最长回文子串
Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
分析：
最长回文子串，解法有几种，主要还是考察动态规划。
设f(i,j)，表示区间[i,j]是否回文，回文则为1，否则为0。f(i,j)的关系表示如下：
代码：
class Solution{
public:
string longestPalindrome(string s){
int len=s.length();
int f[len][len];
memset(f,0,len*len*sizeof(int));
int maxL=1,start=0;
for(int i=0;i<len;i++){
f[i][i]=1;
for(int j=0;j<i;j++){ // j<i
f[j][i]=(s[j]==s[i] && (j+1==i || f[j+1][i-1]));
if(f[j][i] && maxL<(i-j+1)){
maxL=i-j+1;
start=j;
}
}
}
return s.substr(start,maxL);
}
};