传送门 https://leetcode-cn.com/problems/longest-palindromic-substring/
题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
输入: “cbbd”
输出: “bb”
题解：
个人超时算法(滑动窗口算法，易于理解）
思路：从某一窗口长度开始，从0滑动到n-1的位置，判断子串是否为回文，再递增窗口长度。（窗口长度从1开始最一般，下面算法为从2开始）
int check(string s) //判断是否为回文
{
int n = s.size();
int k = n/2;
if(k==0)
{
return 1;
}
else
{
int i=0,f=1;
for(i; i<k; i++)
{
if(s[i]!=s[n-i-1])
{
f=0;
break;
}
}
if(f==1)
{
return 1;
}
else
{
return 0;
}
}
}
string longestPalindrome(string s)
{
int len = s.size();
if(len<=1)
{
return s;
}
string str = "";
str+=s[0];
str+=s[1];
int f=0;
for(int i=2; i<len + 1; i++)
{
for(int j=0; j<len-i+1 ; j++)
{
int k=0;
string ss="";
while(k<i) //可用substr函数代替
{
ss+=s[j+k];
k++;
}
if(check(ss))
{
f=1;
str = ss;
break;
}
}
}
if(f==1)
{
return str;
}
str="";
str+=s[0];
return str;
}
动态规划算法
思路：核心思想在于避免验证回文时的不必要的重复计算。从左往右验证，找出最长回文子串的开始与结束位置。
递推公式为 P(i,j)=(s[i] == s[j]) && (P[i-1][j+1])
PS：需考虑字母数为偶数回文的特殊情况，和确定判断条件。
class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
if(len <= 1)
return s;
int left=0,right=0;
int book[1000][1000]={0}; //1符合，0不符合
for(int i=0;i<len;i++){
book[i][i]=1; //单个字母为回文
for(int j=i-1;j>=0;j--){
book[i][j] = (s[i] == s[j]) && (book[i-1][j+1] || i-j==1); //注意i-j==1条件不能少
//cout<<j<<' '<<i<<' '<<book[i][j]<<endl;
if(book[i][j] && (i-j)>(right-left)){
left = j;
right = i;
}
}
}
string longest="";
longest=s.substr(left,right-left+1);
return longest;
}
};
中心扩展算法
思路：由于回文关于中心对称，所以回文可以从中心展开，其中，共有2*n-1个中心（考虑字母数为偶数的回文）
难点：expandAroundCenter()函数的返回值计算与start和end位置的确定。
class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
if(len<=1)
return s;
int start=0,end=0;
for(int i=0;i<len;i++){
int len1 = expandAroundCenter(s,i,i);
int len2 = expandAroundCenter(s,i,i+1);
//cout<<i<<' '<<len1<<' '<<len2<<endl;
int len = len1 > len2?len1:len2;
if(len > end-start){
if(len==len1){ //进一步归纳，len==len2情况的计算符合所有情况
start = i-len/2;
end = i + len/2;
}else{
start=i- (len-1)/2;
end=i + len/2;
}
}
}
string longest="";
longest=s.substr(start,end-start+1);
return longest;
}
int expandAroundCenter(string s,int left,int right){
while(left>=0 && right<s.size() &&s[left]==s[right]){
left--;right++;
}
return right-left-1; //注意长度不是right-left+1
}
};