Description
給定一個(gè)字符串 s圆雁，找到 s 中最長的回文子串忍级。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案伪朽。
示例 2：
輸入: "cbbd"
輸出: "bb"
這個(gè)題是比較基礎(chǔ)的題目轴咱，有很多中方法，個(gè)人覺得簡單的就是暴力法跟中心擴(kuò)展法烈涮，但是暴力在leetcode上面智能過41個(gè)case朴肺。所以這里我主要介紹下中心擴(kuò)展的方法。
例如一個(gè)字符串s="abbbabba"
那么他的中心無非有兩種坚洽，一種是基數(shù)性質(zhì)的戈稿，比如這個(gè)字符串里面的bab，a就是一個(gè)中心讶舰，第二中就是偶數(shù)為中心的鞍盗，比如‘bb’這種的，由這兩種格式的中心向兩側(cè)進(jìn)行擴(kuò)展绘雁，那哪一個(gè)擴(kuò)展出來的子串的長度長長橡疼，極為最長的回文子串(最長回文子串是中心對稱的)，所以這樣即可得出結(jié)果庐舟，下面是主要的c++代碼
class Solution
{
public:
string longestPalindrome(string s)
{
//判斷空字符串的情況
if (s == "")
{
return "";
}
string result("");
int sSize = int(s.size());
//選擇一個(gè)中心點(diǎn)欣除，向兩側(cè)擴(kuò)展
for (int i = 0; i < sSize; i++)
{
//奇數(shù)組情況
string tmpStr = expandHelper(s, i, i);
//偶數(shù)組情況
string tmpStr2 = expandHelper(s, i, i + 1);
if (int(tmpStr.size()) > int(result.size()))
{
result = tmpStr;
}
if (int(tmpStr2.size()) > int(result.size()))
{
result = tmpStr2;
}
}
return result;
}
string expandHelper(string &s, int left, int right)
{
int sSize = int(s.size());
while (left >= 0 && right < sSize && s[left] == s[right])
{
left--;
right++;
}
//小心s[left] != s[right]
return (s.substr(left + 1, right - left - 1));
}
};
