3.4　最長回文子串

前面講的是不同數據結構下的回文判斷，并且都是難度級別為簡單的題目。這一節來講一道力扣（LeetCode）中難度級別為中等的題目。

題目描述（第5題）

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

示例1

輸入："babad"

輸出："bab"

注意："aba" 也是一個有效答案。

示例2

輸入："cbbd"

輸出："bb"

思路

暴力法是直接枚舉出所有的子串，然后判斷是否回文，用一個變量記錄最大回文字符串即可。找出所有子串的時間復雜度為O(n2)，判斷回文的時間復雜度為O(n)，因此這種算法的時間復雜度是O(n3)，下面考慮優化。

可以使用一種叫作“中心擴展法”的算法。由回文的性質可以知道，回文一定有一個中心點，從中心點向左和向右所形成的字符序列是一樣的，并且如果字符串的長度為偶數的話，中心點在中間的兩個字符的中間位置（不對應具體字符）；如果是奇數的話，則中心點會在中間的字符上。

明白了這一點之后，我們進行一次遍歷，然后對于每一個點，我們都認為它或它和它的下一個字符是中心點，然后我們從中心不斷擴展即可。毫無疑問，這種算法是完備且正確的。

當然這道題也可以使用動態規劃來解決，這里暫時不考慮這種解法，讀者不妨自己使用動態規劃試做一下。

代碼

復雜度分析

●　時間復雜度：枚舉所有中心點的時間復雜度為O(n)，extend函數的時間復雜度仍然是O(n)，因此總的時間復雜度為O(n2)，其中n為字符串的長度。

●　空間復雜度：O(1)。

擴展

你可以使用動態規劃來解決這個題目嗎？