Given a string?s, find the longest palindromic substring in?s.
You may assume that the maximum length of?s?is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
如果事先知道子串長(zhǎng)度鳍贾，可以從左右往里判斷字符是否相等耻台，可本題無(wú)法事先得知子串長(zhǎng)度。
于是將遇到的字符當(dāng)作“最中間”向外擴(kuò)展成了比較合理的選項(xiàng)蔗衡。開始考慮的是分為奇偶回文，如例子中的兩種情況涧狮。后來(lái)看到一種更簡(jiǎn)潔的方法避归，每次把所有和最中間字符相同的字符都略去昵慌，等于看成“最中間”所有相等的字符（如果有）看作一體，這樣就省去來(lái)判斷奇偶的步驟涧衙。另外注意到哪工，如果剩余的字符串長(zhǎng)度不超過(guò)當(dāng)前最長(zhǎng)回文長(zhǎng)度的一半，就可以提前跳出循環(huán)了绍撞。
另外正勒，字符串類的題，還是用 C++ 的 string 寫的方便傻铣，以后的算法題打算用C語(yǔ)言 + C++ string 來(lái)寫章贞，省去一些低級(jí)的字符處理。
