力扣5. 最长回文子串
注:子数组或者子字符串求解问题一般基本是用DP算法
最长回文子串的解释:正着读和反着读是一样的。
题目解析:
解法一:动态规划
从回文子串的定义我们可以得出两个结论:
(1)如果说一个子字符串是回文子串,那么给这个子字符串两边分别加一个数,如果这2个数相等,那么这个新的子字符串也是回文子串。
(2)回文子串的开始和结束位置的字符一定是相等的。
我们可以用i来表示一个子字符串的起始位置,j来表示一个子字符串的结束位置,用一个二维数组来存储i和j之间的子字符串是否是回文子串。看到这可以看出这个问题和背包问题很像。
根据刚才分析得出的结论我们可知:
dp[i][j] = dp[i+1][j-1] && i和j位置的值是否相等
注:dp[i][j]表示以i开头,以j结尾的子字符串是否是回文子串。
那么我们从哪里进入动规入口呢,很明显我们可以知道:当i和j的位置是同一个时,也就是单个字符时,肯定是一个回文子串。
因此我们可以现在表中斜对角的地方都先写上T(True),然后进行递推。这里有一个问题,我们的递推顺序(也就是扫描顺序)是怎么样子的?
首先我们来下面这种扫描方法
很明显,这种扫描方法是错误的,因为我们要确定一个子字符串是否是回文子串,我们必须先知道它中间的子字符串是否是回文子串【也就是我们必须先知道表中当前位置(i,j)的斜下方位置(i+1,j-1)的值】。但是现在这种扫描方法在要计算 dp[i][j]的值时,并不知道此时 dp[i+1][j-1]的值,所以不能这样扫描
正确的扫描方法有如下两种(任选其一进行扫描即可
):
在判断子字符串是否时回文子串的同时,我们应该设置一个变量去记录时回文子串的子字符串的长度,并且不断的用更大的值去更新当前长度。
动态规划代码如下:
注:在写递推代码时,回文子串长度为2和1时无法用状态转移方程得出,因此需做特殊处理。
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
if (size <=1 ) return s; //边界条件处理
int len=1; //记录回文子串的长度,回文子串的最小长度为1。
int start=0; // 回文子串的开始位置
int end;
vector<vector<int>>dp (size,vector<int>(size,0));
for(int i = 0;i<size;i++) dp[i][i]=1; //设置表格中对角线位置的值
for (int j = 1; j<size;j++) //i是开始位置,j是结束位置
{
for (int i=0;i<j;i++)
{
if (s[i] == s[j])
{
if (j-i<3)
dp[i][j] = 1; //特殊情况处理
else
dp[i][j] = dp[i+1][j-1];
}
if ( dp[i][j] ) //更新长度
{
if(j-i+1 > len)
{
len = j-i+1;
start = i;
}
}
}
}
return s.substr(start,len);
}
};
解法二:中心扩展法
待续……
参考:https://www.bilibili.com/video/BV1SE411y7RW?from=search&seid=2950817619903450615