問題
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"
分析
遍歷字符串蹂喻。從當前字符向兩邊擴展限佩，找到一個局部最長的回文字符串奏窑，再更新全局的最長的回文字符串的長度即可。
要注意回文字符串要分成兩種類型：
- 長度為奇數(shù)曼追，例如acbdbca舟陆，ddddd捞挥。對稱軸為一個字符滩届；
- 長度為偶數(shù)，例如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设褐，長度為奇數(shù)的回文字符串
int len2 = expandFromCenterLength(s, i, i + 1); // 類型2颠蕴，長度為偶數(shù)的回文字符串
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);
}
};
