找出字符串中最长的脚用一开头嘚成语来写回文串暴力法及Manacher算法这里不列了,第一种不推荐另一种想深入研究可自行搜索~~
1 先介绍一下中心扩散思想:
从每一个位置,姠二边扩散即可
2 基于中心思想利用动态规划,这里可推出具体的公式来
d[j][i]表示字符串中第j个字符到第i个字符是否为回文串则d[j-1][i+1] 可转化为:
當j-1= i+1 的时候就是两边界相等的时候,移项得j-i=2,所有有j-i<=2的时候就是区间不存在的情况这个时候dp[i][j]是没有意义的。(j-1-(i+1)+1<2时此时[i+1,j-1]的区间,此时长度為2或3只需要判断头尾2个字符相等即可)