给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例 2：
输入: "cbbd"
输出: "bb"来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
方法1：动态规划
最优子结构：当一个串是一个回文串的时候，在其头尾各加一个相同的字符组成的新字符串依旧是一个回文串
dp[i][j]=1，代表从下标i到下标j组成的字符串是一个回文串
如果s[i]==s[j]&&dp[i+1][j-1]==1，那么dp[i][j]=1
初始化：
1.对于一个字符的回文串：dp[i][i]=1
2.对于两个字符的回文串：如果s[i]==s[i+1]，那么dp[i][i+1]=1
对于三个字符的回文串：如果s[i]==s[j]&&dp[i+1][j-1]==1，那么dp[i][j]=1
时间复杂度：O(N^2)
空间复杂度：O(N^2)
class Solution {
public:
string longestPalindrome(string s)
{
if(s.size()==)
return "";
if(s.size()==)
return s;
if(s.size()==&&s[]==s[])
return s;
int n=s.length();
int dp[n+][n+];
memset(dp,,sizeof(dp));
int ans=;
int start=;
for(int i=;i<n;i++)
{
dp[i][i]=;
}
for(int i=;i<n-;i++)
{
if(s[i]==s[i+])
{
dp[i][i+]=;
ans=;
start=i;
}
}
int l=;
while(l<=n)
{
for(int i=;i<n-l+;i++)
{
int j=i+l-;
if(dp[i+][j-]==&&s[i]==s[j])
{
dp[i][j]=;
start=i;
ans=l;
}
}
l++;
}
return s.substr(start,ans);
}
};
方法2：中心扩展法
将每个字符当作回文串的中心，然后往两边扩展，取扩展得到的回文串的最大值就是最长回文子串
考虑到回文串的奇偶情况，我们可以算两种情况：以一个字符为回文串的中心，以两个字符为回文串的中心，然后去二者最大值就可以
时间复杂度：O(N^2),以每个字符为中心需要遍历一次，然后每次都需要往两边扩展
空间复杂度：O(1),只需要用到一些常量
class Solution {
public:
int f1(string str,int left,int right,int n)
{
int c=;
//cout<<"left="<<left<<" right="<<right<<" n="<<n<<endl;
left--;
right++;
while(left>=&&right<n&&str[left]==str[right])
{
left--;
right++;
c+=;
}
return c;
}
int f2(string str,int left,int right,int n)
{
int c=;
if(str[left]==str[right])
c=;
else
{
c=;
return c;
}
left--;
right++;
while(left>=&&right<n&&str[left]==str[right])
{
left--;
right++;
c+=;
}
return c;
}
string longestPalindrome(string s)
{
int n=s.size();
if(n==)
return "";
if(n==)
return s;
if(n==&&s[]==s[])
return s;
int ans=;
int start=;
for(int i=;i<n-;i++)
{
int x1=f1(s,i,i,n);
int x2=f2(s,i,i+,n);
//cout<<"i="<<i<<" x1="<< x1<<" x2="<<x2<<endl;
if(max(x1,x2)>ans)
{
ans=max(x1,x2);
//cout<<"ans="<<ans<<endl;
if(ans%==)
start=i-ans/;
else
start=i-(ans-)/;
//cout<<"start="<<start<<endl;
}
}
return s.substr(start,ans);
}
};
还有一个解决方案是马拉车算法
时间复杂度为O(N)!!!
但是我目前也没有掌握，就没有贴出来，怕误导别人