为什么单独把这道题拿出来，是因为我在各大公司的校招面试中，遇到多次这道题目，比如阿里优酷，字节跳动以及猿辅导，所以想把这道题整体拿出来单独讨论，以便为以后再遇到此类题目做一个参考。

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

思路

思路1#

基于中心点枚举的算法，时间复杂度是O(n^2)。

先确定中间的点，这里包括两种，中间只有一个元素，或者中间有两个元素。

思路2#

基于动态规划的算法，时间复杂度 O(n^2)，会耗费额外的 O(n^2) 的空间复杂度。

dp[i][j]，i <= j，表示从i到j是否是回文串，

状态转移方程是dp[i][j] = dp[i + 1][j - 1] && s[i] = s[j]。

思路3#

使用 Manancher's Algorithm，可以在 O(n) 的时间内解决问题。

参考资料：。

这个方法虽然最优，感觉一般人很难想到。

代码

方法1

方法2