讀完本文骡湖，你可以去力扣拿下如下題目：
-----------
回文串是面試常常遇到的問題（雖然問題本身沒啥意義），本文就告訴你回文串問題的核心思想是什么峻厚。
首先响蕴，明確一下什：回文串就是正著讀和反著讀都一樣的字符串。
比如說字符串 aba 和 abba 都是回文串惠桃，因為它們對稱浦夷，反過來還是和本身一樣辖试。反之，字符串 abac 就不是回文串军拟。
可以看到回文串的的長度可能是奇數(shù)剃执，也可能是偶數(shù)，這就添加了回文串問題的難度懈息，解決該類問題的核心是雙指針肾档。下面就通過一道最長回文子串的問題來具體理解一下回文串問題：
string longestPalindrome(string s) {}
一、思考
對于這個問題辫继，我們首先應(yīng)該思考的是怒见，給一個字符串 s，如何在 s 中找到一個回文子串姑宽？
有一個很有趣的思路：既然回文串是一個正著反著讀都一樣的字符串遣耍，那么如果我們把 s 反轉(zhuǎn)，稱為 s'炮车，然后在 s 和 s' 中尋找最長公共子串舵变，這樣應(yīng)該就能找到最長回文子串。
比如說字符串 abacd瘦穆，反過來是 dcaba纪隙，它的最長公共子串是 aba，也就是最長回文子串扛或。
但是這個思路是錯誤的绵咱，比如說字符串 aacxycaa，反轉(zhuǎn)之后是 aacyxcaa熙兔，最長公共子串是 aac悲伶，但是最長回文子串應(yīng)該是 aa。
PS：我認真寫了 100 多篇原創(chuàng)住涉，手把手刷 200 道力扣題目麸锉，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新秆吵。建議收藏淮椰，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了纳寂。
雖然這個思路不正確主穗，但是這種把問題轉(zhuǎn)化為其他形式的思考方式是非常值得提倡的。
下面毙芜，就來說一下正確的思路忽媒，如何使用雙指針。
尋找回文串的問題核心思想是：從中間開始向兩邊擴散來判斷回文串腋粥。對于最長回文子串晦雨，就是這個意思：
for 0 <= i < len(s):
找到以 s[i] 為中心的回文串
更新答案
但是呢架曹，我們剛才也說了，回文串的長度可能是奇數(shù)也可能是偶數(shù)闹瞧，如果是 abba這種情況绑雄，沒有一個中心字符，上面的算法就沒轍了奥邮。所以我們可以修改一下：
for 0 <= i < len(s):
找到以 s[i] 為中心的回文串
找到以 s[i] 和 s[i+1] 為中心的回文串
更新答案
PS：讀者可能發(fā)現(xiàn)這里的索引會越界万牺，等會會處理。
二洽腺、代碼實現(xiàn)
按照上面的思路脚粟，先要實現(xiàn)一個函數(shù)來尋找最長回文串，這個函數(shù)是有點技巧的：
string palindrome(string& s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.size()
&& s[l] == s[r]) {
// 向兩邊展開
l--; r++;
}
// 返回以 s[l] 和 s[r] 為中心的最長回文串
return s.substr(l + 1, r - l - 1);
}
為什么要傳入兩個指針 l 和 r 呢蘸朋？因為這樣實現(xiàn)可以同時處理回文串長度為奇數(shù)和偶數(shù)的情況：
for 0 <= i < len(s):
# 找到以 s[i] 為中心的回文串
palindrome(s, i, i)
# 找到以 s[i] 和 s[i+1] 為中心的回文串
palindrome(s, i, i + 1)
更新答案
下面看下 longestPalindrome 的完整代碼：
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i++) {
// 以 s[i] 為中心的最長回文子串
string s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 為中心的最長回文子串
string s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
至此核无，這道最長回文子串的問題就解決了，時間復(fù)雜度 O(N^2)藕坯，空間復(fù)雜度 O(1)团南。
PS：我認真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目炼彪，全部發(fā)布在 labuladong的算法小抄已慢，持續(xù)更新。建議收藏霹购，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了朋腋。
值得一提的是齐疙，這個問題可以用動態(tài)規(guī)劃方法解決，時間復(fù)雜度一樣旭咽，但是空間復(fù)雜度至少要 O(N^2) 來存儲 DP table贞奋。這道題是少有的動態(tài)規(guī)劃非最優(yōu)解法的問題。
另外穷绵，這個問題還有一個巧妙的解法轿塔，時間復(fù)雜度只需要 O(N)，不過該解法比較復(fù)雜仲墨，我個人認為沒必要掌握勾缭。該算法的名字叫 Manacher's Algorithm（馬拉車算法），有興趣的讀者可以自行搜索一下目养。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章俩由，手把手帶刷 200 道力扣題目，建議收藏癌蚁！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star幻梯，歡迎標星兜畸！
