最后更新于
最后更新于
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
示例 2:
回文串一定是对称的, 所以我们可以每次选择一个中心, 进行左右扩展, 判断左右字符是否相等即可.
由于存在对称中心是奇数或偶数的情况, 所有共有个中心, 是字符串的长度.
这种方法是比较直观的方法, 时间复杂度, 空间复杂度
动态规划的解法参考:
第一篇对动态规划的状态, 状态转移方程, 边际条件描述的更清楚, 并且考虑了空间优化的问题, 降低了空间复杂度.
第二篇详细讲解了, 根据状态转移方程的特点, 迭代的方向的选择及其原因, 也为第一篇文中的空间优化的循环方式, 做了更为清晰的解释.
此题采用动态规划的思路, 空间复杂度为, 下面的代码为空间优化的版本, 对应的空间复杂度为.
Manacher算法参考.