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));
}
};