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)。

扩展

你可以使用动态规划来解决这个题目吗？