最長迴文子串

給定一個字元串 s，找到 s 中最長的迴文子串。你可以假設 s 長度最長為1000。

示例:

輸入: "babad"

輸出: "bab"

註意: "aba"也是有效答案

示例:

輸入: "cbbd"

輸出: "bb"

哎，看到這個題目深感痛苦，華為筆試第一題就是這題，只不過是返回最大長度，
然後不會做，心疼。
然後在leetcode找到了這道題，從而發誓要把LeetCode每一道題刷完。

暴力解法，這個容易理解，從頭開始遍歷字元串，每遇到一個字元，就從該
字元開始前後判斷是否是迴文字元串，奇數長度則該字元為中心，偶數長度
就是該字元和下一個字元為中心。
時間複雜度O（n2）

class Solution {
public:
string longestPalindrome(string s) {
　　if(s=="") return "";
　　int max=1;
　　string a="";
　　string res="";
　　for(int i=0;i<s.size();i++)
　　{
　　　　a="";
　　　　int x=i-1;
　　　　int y=i+1;
　　　　int length=1;
　　　　a=a+s[i];
　　　　while(x>-1&&y<s.size()) //這個方法有點笨，先判斷是奇數情況
　　　　{
　　　　　　if(s[x]==s[y])
　　　　　　{
　　　　　　a=s[x]+a+s[y];
　　　　　　x--;
　　　　　　y++;
　　　　　　length+=2;
　　　　　　}
　　　　　　else break;
　　　　}
　　　　if(length>=max)
　　　　{
　　　　　　res=a;
　　　　　　max=length;
　　　　}
　　}
　　for(int i=0;i<s.size();i++)
　　{
　　　　a="";
　　　　int x=i;
　　　　int y=i+1;
　　　　int length=0;
　　　　while(x>-1&&y<s.size()) //後判斷是偶數情況
　　　　{
　　　　　　if(s[x]==s[y])
　　　　　　{
　　　　　　　　a=s[x]+a+s[y];
　　　　　　　　x--;
　　　　　　　　y++;
　　　　　　　　length+=2;
　　　　　　}
　　　　　　else break;
　　　　}
　　　　if(length>max)
　　　　{
　　　　　　res=a;
　　　　　　max=length;
　　　　}
　　}
　　return res;
}
};

上面這個暴力解法，果然94個樣例用了1196ms，明顯時間複雜度過高。

優化解法

試想，一個字元串是迴文字元串，那個有可能是abba，或者abcba情況，

嘗試用一個迴圈解決問題，先判斷其是否是第一種情況(即是是否有連續重覆字元，有則其肯定是迴文字元串子串)，

然後假設不符合上一情況後，再判斷第二種情況，即可減少迴圈次數。

class Solution {
public:
string longestPalindrome(string s) {
　　if(s=="") return "";
　　if(s.size()==1) return s;
　　int len=1;
　　int min=0;
　　for(int i=0;i<s.size();)
　　{
　　　　if(s.size()-i<=len/2) break;  //如果剩下的字元串長度都少於或等於len的一半，不用判斷了，len肯定為最長了
　　　　int l=i;
　　　　int r=i;
　　　　while(r<s.size()-1 && s[r]==s[r+1]) r++;　　//判斷連續重覆字元，有多少個重覆字元長度就增長多少
　　　　i=r+1;　　//不符合連續重覆字元後，由r位置定位i，並且s[r]肯定不等於s[r+1]了，則可以判斷s[r+1]與s[l-1]的關係了
　　　　while(r<s.size()-1 && l>0 && s[r+1]==s[l-1])
　　　　{
　　　　　　r++;　　　　　　　　//擴展
　　　　　　l--;
　　　　}
　　　　if(r-l+1>len)　　　　//判斷
　　　　{
　　　　　　min=l;　　　　//min定位最長迴文字元串開頭
　　　　　　len=r-l+1;
　　　　}
　　}
　　return s.substr(min,len);　　
}
};

然後提交4ms過了全部樣例，當是優化了吧。

還有一個尾碼樹是解決這類字元串問題的極佳方法，可以把時間複雜度降為O（n），

等我看懂原理了再來更博詳解。