647. 回文子串
647. 回文子串
题目描述：
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
解题思路：
算法思路：
我们可以先「预处理」⼀下，将所有⼦串「是否回⽂」的信息统计在
dp
表⾥⾯，然后直接在表
⾥⾯统计
true
的个数即可。
1.
状态表⽰：
为了能表⽰出来所有的⼦串，我们可以创建⼀个
n * n
的⼆维
dp
表，只⽤到「上三⻆部分」
即可。
其中，
dp[i][j]
表⽰：
s
字符串
[i, j]
的⼦串，是否是回⽂串。
2.
状态转移⽅程：
对于回⽂串，我们⼀般分析⼀个「区间两头」的元素：
i.
当
s[i] != s[j]
的时候：不可能是回⽂串，
dp[i][j] = 0
；
ii.
当
s[i] == s[j]
的时候：根据⻓度分三种情况讨论：
•
⻓度为
1
，也就是
i == j
：此时⼀定是回⽂串，
dp[i][j] = true
；
•
⻓度为
2
，也就是
i + 1 == j
：此时也⼀定是回⽂串，
dp[i][j] = true
；
•
⻓度⼤于
2
，此时要去看看
[i + 1, j - 1]
区间的⼦串是否回⽂：
dp[i][j]
= dp[i + 1][j - 1]
。
综上，状态转移⽅程分情况谈论即可。
3.
初始化：
因为我们的状态转移⽅程分析的很细致，因此⽆需初始化。
4.
填表顺序：
根据「状态转移⽅程」，我们需要「从下往上」填写每⼀⾏，每⼀⾏的顺序⽆所谓。
5.
返回值：
根据「状态表⽰和题⽬要求」，我们需要返回
dp
表中
true
的个数。
解题代码：
class Solution {
public:
int countSubstrings(string s) {
int n=s.size();
vector<vector<bool>>dp(n,vector(n,false));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
{
if(i==j)dp[i][j]=true;
else if(i+1==j)dp[i][j]=true;
else dp[i][j]=dp[i+1][j-1];
}
}
}
int ret=0;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(dp[i][j]==true)
ret++;
}
}
return ret;
}
};5. 最长回文子串
5. 最长回文子串
题目描述：
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
解题思路：
647. 回文子串
https://leetcode.cn/problems/palindromic-substrings/
在647题的基础上遍历所有dp表中为true的初始位置和长度
解题代码：
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
vector<vector<bool>>dp(n,vector(n,false));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
{
if(i==j)dp[i][j]=true;
else if(i+1==j)dp[i][j]=true;
else dp[i][j]=dp[i+1][j-1];
}
}
}
int length=1;
int begin=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(dp[i][j]==true&&length<j-i+1)
{
length=max(j-i+1,length);
begin=i;
}
}
return s.substr(begin,length);
}
};
