最长回文子串
前段时间太忙所以就断更了,尽量从今天开始继续每日一更。
最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
方法一:动态规划法
①分解子序列。若要s[i]到s[j]为回文串的话,那么需要s[i+1]到s[j-1]为回文串并且s[i]==s[j]。那么我们就需要将s[i+1]到s[j-1]是否为回文串以及回文串的长度做出记录。
②基例。若“aba”的情况的话与我们分解子序列的求法是一致的,但是“aa”这样的情况的话显然去使用分解子序列的求法就会有问题,所以我们就需要单独处理这样子的基例。
③为了记录s[i]到s[j]的回文长度,那么我们需要一个二维数组,A[i][j]表示s[i]到s[j]的回文长度,若不是则为0。
方法二:中心扩展法
思路:回文串本身就是中点为中心左右对称的,所以这里可以以每一个字符为中心寻找回文串,但需要注意一点,如果回文串为偶数的话,那么他的对称中心在两字符之间,所以在中心扩展时需要把两字符之间也加入进来。故需要进行n+n-1次的中心扩展。