问题
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
例子
**Input: **"babad"
**Output: **"bab"
**Note: **"aba" is also a valid answer.
Input: "cbbd"
**Output: **"bb"
分析
遍历字符串。从当前字符向两边扩展，找到一个局部最长的回文字符串，再更新全局的最长的回文字符串的长度即可。
要注意回文字符串要分成两种类型：
- 长度为奇数，例如acbdbca，ddddd。对称轴为一个字符；
- 长度为偶数，例如acbbca，dddddd。对称轴为两个相同的字符
要点
- 从当前字符向两边扩展
- 回文字符串分类
时间复杂度
O(n^2)
空间复杂度
O(1)
代码
class Solution {
public:
// 从当前字符向两边扩展，找到一个局部最长的回文字符串
int expandFromCenterLength(const string &s, int beg, int end)
{
while (beg >= 0 && end < s.length() && s[beg] == s[end])
{
beg--;
end++;
}
return end - beg - 1;
}
string longestPalindrome(string s) {
int beg = 0, end = 0;
for (int i = 0; i < s.length(); i++)
{
int len1 = expandFromCenterLength(s, i, i); // 类型1，长度为奇数的回文字符串
int len2 = expandFromCenterLength(s, i, i + 1); // 类型2，长度为偶数的回文字符串
int len = max(len1, len2);
if (len > end - beg + 1)
{
beg = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substr(beg, end - beg + 1);
}
};
