題目描述：
給定一個字符串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為1000。
示例 1：
輸入: "babad"輸出: "bab"注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"輸出: "bb"
摘要：
這篇文章是為中級讀者而寫的。它介紹了迴文，動態規劃以及字符串處理。請確保你理解什麼是迴文。迴文是一個正讀和反讀都相同的字符串，例如，“aba” 是迴文，而 “abc” 不是。
方法一、最長公共子串：
常見錯誤
有些人會忍不住提出一個快速的解決方案，不幸的是，這個解決方案有缺陷（但是可以很容易地糾正）：
反轉 S，使之變成 S′。找到 S 和 S′ 之間最長的公共子串，這也必然是最長的迴文子串。
這似乎是可行的，讓我們看看下面的一些例子。
例如，S = “caba”，S′ = “abac”：
S 以及 S′ 之間的最長公共子串為 “aba”，恰恰是答案。
讓我們嘗試一下這個例子：S = “abacdfgdcaba”，S′ = “abacdgfdcaba”：
S 以及 S′ 之間的最長公共子串為 “abacd”，顯然，這不是迴文。
算法
我們可以看到，當 S 的其他部分中存在非迴文子串的反向副本時，最長公共子串法就會失敗。為了糾正這一點，每當我們找到最長的公共子串的候選項時，都需要檢查子串的索引是否與反向子串的原始索引相同。如果相同，那麼我們嘗試更新目前為止找到的最長迴文子串；如果不是，我們就跳過這個候選項並繼續尋找下一個候選。
這給我們提供了一個複雜度為 O(n^2) 動態規劃解法，它將佔用 O(n^2) 的空間（可以改進為使用 O(n) 的空間）。
方法二、暴力法：
很明顯，暴力法將選出所有子字符串可能的開始和結束位置，並檢驗它是不是迴文。
複雜度分析
- 時間複雜度：O(n^3)，假設 n 是輸入字符串的長度，則
- 為此類子字符串(不包括字符本身是迴文的一般解法)的總數。因為驗證每個子字符串需要 O(n) 的時間，所以運行時間複雜度是 O(n^3)。
- 空間複雜度：O(1)。
方法三、動態規劃：
為了改進暴力法，我們首先觀察如何避免在驗證迴文時進行不必要的重複計算。考慮 “ababa” 這個示例。如果我們已經知道 “bab” 是迴文，那麼很明顯，“ababa” 一定是迴文，因為它的左首字母和右尾字母是相同的。
複雜度分析
- 時間複雜度：O(n^2)， 這裡給出我們的運行時間複雜度為 O(n^2) 。
- 空間複雜度：O(n^2)， 該方法使用 O(n^2) 的空間來存儲表。
補充練習
你能進一步優化上述解法的空間複雜度嗎？
方法四、中心擴展算法：
事實上，只需使用恆定的空間，我們就可以在 O(n^2) 的時間內解決這個問題。
我們觀察到迴文中心的兩側互為鏡像。因此，迴文可以從它的中心展開，並且只有 2n - 1 個這樣的中心。
你可能會問，為什麼會是 2n - 1，而不是 n 箇中心？原因在於所含字母數為偶數的迴文的中心可以處於兩字母之間（例如 “abba” 的中心在兩個 ‘b’ 之間）。
複雜度分析
- 時間複雜度：O(n^2)， 由於圍繞中心來擴展迴文會耗去 O(n)
- O(n) 的時間，所以總的複雜度為 O(n^2)。
- 空間複雜度：O(1)。
方法五、Manacher 算法：
還有一個複雜度為 O(n) 的 Manacher 算法，你可以在這裡找到詳盡的解釋。然而，這是一個非同尋常的算法，在45分鐘的編碼時間內提出這個算法將會是一個不折不扣的挑戰。但是，請繼續閱讀並理解它，我保證這將是非常有趣的。
閱讀更多 領釦網 的文章
