给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
解题思路一：动态规划
这道题的动态规划解法之前在学动态规划的时候就已经讲过了，这里就不再赘述了，具体可以参考之前的笔记！
class Solution {
public:
string longestPalindrome(string s) {
// 定义dp二维数组，dp[j][i]表示从[j, i]区间是否为回文字符串
bool dp[1000][1000] = { 0 };
int maxlen = 0, maxindex = 0;
for(int i = 0; i < s.size(); ++i)
{
for(int j = 0; j <= i; ++j)
{
// 状态转移方程
if(s[i] == s[j])
{
if(i == j || j + 1 == i)
dp[j][i] = true;
else
dp[j][i] = dp[j + 1][i - 1];
if(dp[j][i] && i - j + 1 > maxlen) // 是回文字符串并且长度更长了再更新
{
maxlen = i - j + 1;
maxindex = j;
}
}
}
}
return s.substr(maxindex, maxlen);
}
};解题思路二：中心扩散法
之前我们在动态规划笔记中提到，字符串的常见题解方法还有一个中心扩散法（至于一个马拉车算法就不讲了，学习成本高，使用率太低），它其实借助的就是回文字符串的特性，由中心自发的向外扩散寻找回文字符串，直到不符合要求！
假设此时我们遍历到字符串的 i 位置，然后定义两个指针 left 和 right 指向该位置，两指针从该位置分别向左和向右出发，每次走一格，判断 s[left] 是否等于 s[right]，是的话说明此时就是 [left, right] 区间就是一个回文字符串，则判断是否需要更新最大长度以及回文字符串的起始位置，一直重复上述动作直到判断不符合或者越界了为止！
但是上面操作有个问题，就是只考虑到了区间是奇数的情况，如果是偶数情况比如字符串 "abbc" 的话，此时 "bb" 这种情况就被忽略了，所以我们需要判断偶数个字符的情况！
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int maxlen = 0, maxindex = 0;
for(int i = 0; i < n; ++i)
{
// 判断奇数情况
int left = i, right = i;
while(left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if(right - left - 1 > maxlen)
{
maxlen = right - left - 1;
maxindex = left + 1;
}
// 判断偶数情况（就起始位置不一样，剩下的操作逻辑都是一样的）
left = i, right = i + 1;
while(left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if(right - left - 1 > maxlen)
{
maxlen = right - left - 1;
maxindex = left + 1;
}
}
return s.substr(maxindex, maxlen);
}
};