算法Code-最长回文子串

微信公众号：glmapper工作室

如有问题或建议，请公众号留言

最近更新：

题目

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

示例:

示例:

思路

一开始是想用最笨的方法来解的，也就是找出所有的字串，然后再对所有的子串进行回文检测，并记录长度。这种方式时间复杂度可想而知，O(n)O(n)O(n)=O(n^3)。所以这种肯定是不能满足我们要求的。

ok，那我们来分析一下这个问题，先把这个问题特殊化；

假如输入的字符串长度就是1

那么这个字符串的最长回文串就是它自己，长度就是1

假如字符串长度为2，它要是回文串的化，就需要两个字符是相等的。

即：s[i] == s[j] 且i-j=1(此处假定i是较大索引位置)

那么对于i－j>1的情况下呢？是不是只要满足下面的条件就可以了：

即:s[i] == s[j]&&s[i-1] == s[j+1]

其实这种思路就是动态规划。关于动态规划的理论性文字就不码了，有兴趣的小伙伴阔以自行学习。下面就针对这个问题码一下代码：