【5】Longest Palindromic Substring 最长回文子串

求字符串的最长回文子串:https://leetcode.com/problems/longest-palindromic-substring

 


 

1.遍历字符串,以当前字符为中心。向两边扩散比对。o(n^2)  .  注意当回文串为奇数偶数情况不一样。

我的臃肿代码:

 

题解的优雅代码:

 

2、动态规划解法

设P[i,j] 表示以i开始以j结束的子串,如果p[i,j]是回文字符串,那么P[i+1,j-1]也是回文字符串。

状态方程和转移方程:

P[i,j]=false 表示子串[i,j]不是回文串。P[i,j]=true表示子串[i,j]是回文串。

P[i,i]=true

P[i,j]  = P[i+1,j-1]  &&  s[i]==s[j]

 

  1. 网上发现的-Manacher算法:   http://www.cnblogs.com/Lyush/p/3221503.html