一，回文子串
题目链接：LCR 020. 回文子串 - 力扣（LeetCode）
【问题描述】
求一个字符串中有多少个回文子串，其中一个字符也算是一个回文子串。
【解法】
动态规划
求一个字符串中回文子串的个数，我么可以找到每个回文子串，然后统计个数即可。
首先定义状态表示：
dp[i]：表示子串[i-j]，是否是回文串。其中下标i<=j。
状态转移方程的推导：
当s[i]!=s[j]时，也就是子串的第一个字符和最后一个字符不相等，那么肯定不是回文串，所以dp[i][j]=false。
当s[i]==s[j]时，在该情况下，又细分三种情况：
- 如果i==j，那么该子串就是一个字符，是回文串，所以dp[i][j]=true。
- 如果i+1==j，也就是该字符串由两个字符构成，且s[i]==s[j]，是回文串，所以dp[i][j]=true。
- 如果i+1<j，表示s[i]和s[j]中还有一些字符，那么dp[i][j]=dp[i+1][j-1]。
初始化dp表时，根据状态表示的定义，我们只会用到dp表主对角线的右上部分，左下部分不会用到，对于状态转移dp[i][j]=dp[i+1][j-1]，我们不需要考虑越界的问题，因为前两种情况已经做了判断。
最后，只需统计dp表中dp[i][j]==true的数量即可。
【代码】
class Solution {
public:
int countSubstrings(string s) {
//dp[i]:子串[i-j]是否是回文串
int n=s.size();
int sum=0;//统计结果
vector<vector<bool>> dp(n,vector<bool>(n,false));
for(int i=n-1;i>=0;i--)
for(int j=i;j<n;j++)
{
if(s[i]!=s[j])
{
dp[i][j]=false;
}
else
{
dp[i][j]=i+1<j?dp[i+1][j-1]:true;
}
if(dp[i][j])
sum++;
}
return sum;
}
};时间复杂度O(N^2），空间复杂度O(N^2）
二，最长回文子串
【题目描述】
求字符串中最长的回文子串。
【解法1】
动态规划
上一题是求回文子串的个数，我们用一个dp表来表示【i-j】是否是回文串。
本题可以直接使用上题 的思路，如果dp[i][j]是回文串，也就是dp[i][j]==true，那么看看该子串的长度是否是最大的，该子串的长度是j-i+1。可以使用一个变量len来记录最长的回文子串的长度，begin来记录该回文串的开始位置i。最后使用substr就可以获取到该子串。
【代码】
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
int len=0,begin=0;
for(int i=n-1;i>=0;i--)
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
dp[i][j]=i+1<j?dp[i+1][j-1]:true;
if(dp[i][j])
{
if(len<j-i+1)
{
len=j-i+1;
begin=i;
}
}
}
return s.substr(begin,len);
}
};时间复杂度：O(N^2），空间复杂度O(N^2)
【解法2】
中心扩展算法
求最长的回文子串。我们可以从一个字符出发，求出它作为中心所能形成的最长回文串的长度。
用一个变量i来记录遍历到字符串的哪一个为位置。
每遍历到一个位置，向两边扩展，用两个变量left和right来记录扩展位置的下标。
回文子串的长度可能是奇数，也可能是偶数，所以需要计算两次：
1，回文子串的长度是奇数，让left=i-1，right=i+1，向两边扩展，如果s[left]==s[right]，
left--，right++。最后回文子串的长度就是right-left-1。
2，回文子串的长度是偶数，让left=i-1，right=i（left=i，right=i+1也可以），同理，如果s[left]==s[right]，left--,right++。最后回文子串的长度就是right-left-1。
记录这两种情况下回文子串最长的长度，以及该回文子串开始的下标。
【代码】
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
int begin=0,len=0;
for(int i=0;i<n;i++)
{
//奇数扩展
int left=i,right=i;
while(left>=0&&right<n&&s[left]==s[right])
{
left--;
right++;
}
if(len<right-left-1)
{
len=right-left-1;
begin=left+1;
}
//偶数扩展
left=i-1,right=i;
while(left>=0&&right<n&&s[left]==s[right])
{
left--;
right++;
}
if(len<right-left-1)
{
len=right-left-1;
begin=left+1;
}
}
return s.substr(begin,len);
}
};时间复杂度O(N)，空间复杂度O(1)
三，回文串分割IV
题目链接：1745. 分割回文串 IV - 力扣（LeetCode）
【题目描述】
对于一个字符串，将他分为任意的三个子串，如果存在这三个子串都是回文串，返回true，否则返回false
【解法】
将一个字符串分割成三个子串，可以想象成在一个字符串中，切两刀，分成三部分，而这两“刀”就是下标，我们用下标i,j将字符串分成三个部分，[0,i-1]，[i,j]，[j+1,n-1]，n为字符串长度。
所以只需判断这三个子串是否是回文串即可。而在第一道题中我们使用一个dp表来表示[i-j]子串是否是回文串。所以，在本题中，我们可以使用dp表来做预处理，然后枚举这三个子串：
[0,i-1]，[i,j]，[j,n-1]，判断这三个子串是否是回文串。
【代码】
class Solution {
public:
bool checkPartitioning(string s) {
//dp表存储回文信息【i,j】
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
dp[i][j]=i+1<j?dp[i+1][j-1]:true;
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(dp[i][j]&&i-1>=0&&j+1<n)
if(dp[0][i-1]&&dp[j+1][n-1])
return true;
}
return false;
}
};四，回文串分割II
题目链接：LCR 094. 分割回文串 II - 力扣（LeetCode）
【解法】
动态规划
首先定义状态表示：
dp[i]：表示【0-i】区间的子串，最少的切割次数。
状态转移方程的推导：
如果子串【0-i】本身就是回文串，就不需要切割，即dp[i]=0.
如果子串【0-i】不是回文串，需要切割，我们可以枚举切割的位置j，0<j<=i。其中不用枚举j=0，因为j=0，也就是【0-i】区间。j从i开始枚举，接下来判断【j-i】是否是回文串：
- 如果【j-i】是回文串，那么就找到了一个分割点，dp[i]就等于【0，j-1】区间的最少分割次数+1，
- 即dp[i]=dp[j-1]+1。
- 如果【j-i】不是回文串，就不是一个分割点，继续找分割点。
其中求的是最少的分割次数，所以
dp[i]=min(dp[i],dp[j-1]+1)。
上面的过程 中，会一直判断某一段区间是否是回文串，所以可以用第一道题的思路，用一张表来记录区间【i-j】是否是回文串。
初始化dp表：
不用判断数组越界的问题，因为j是大于0的。
由于求的是最小值，所以不能将数组的初始值设为0，会影响最终结果。需要设为无穷大。
【代码】
class Solution {
public:
int minCut(string s) {
int n=s.size();
//i-j区间是否是回文串
vector<vector<bool>> isPal(n,vector<bool>(n,false));
for(int i=n-1;i>=0;i--)
for(int j=i;j<n;j++)
{
if(s[i]!=s[j])
{
isPal[i][j]=false;
}
else
{
isPal[i][j]=i+1<j?isPal[i+1][j-1]:true;
}
}
//0-i区间最少分割次数
vector<int> dp(n,INT_MAX);
for(int i=0;i<n;i++)
{
//0-i是回文串
if(isPal[0][i])
{
dp[i]=0;
continue;
}
//枚举分割点，求最少分割次数
for(int j=i;j>0;j--)
{
//j-i是回文串
if(isPal[j][i])
{
dp[i]=min(dp[i],dp[j-1]+1);
}
}
}
return dp[n-1];
}
};时间复杂度O(N^2)，空间复杂度O(N^2)
五，最长回文子序列
题目链接：516. 最长回文子序列 - 力扣（LeetCode）
【题目描述】
本题与上面的题不同，本题是求最长的回文子序列的长度，子序列是指元素可以不连续，而前面的子串问题，都是要求元素是连续的。
【解法】
按照常规的思路，我们会定义如下的状态方程：
dp[i]：表示以第i个元素为结尾的所有子序列中，最长的回文子序列的长度。
要想推导dp[i]，一定会与dp[i-1]，dp[i-2]，dp[i-3]......有关，因为是子序列问题，第i个字符可以拼接到第i-1个字符的后面，也可以拼接到第i个字符的后面......所以会需要前面的dp值来更新dp[i]的值。比如需要通过dp[i-1]来推导dp[i]的值，但是dp[i-1]表示的以第i-1个元素为结尾的最长回文子序列的长度，我们将第i个元素拼接到第i-1个元素的后面，无法判断拼接后的子序列是否是回文串，所以无法推导，所以这样的状态表示是不行的。
在“回文子串”题中，我们判断一段区间【i-j】是否是回文串，对于这段区间，我们只关心两个端点的状态，也就是s[i]和s[j]的关系。本题也类似。
首先定义状态标识：
dp[i][j]：表示【i-j】区间中最长的回文子序列的长度。
状态转移方程的推导：
【i i+1 j-1 j】
如果s[i]==s[j]，有三种情况：
- i==j，表示一个字符，是回文串，长度为1，所以dp[i]=1。
- i+1==j，表示两个 字符相邻并且相等，那么回文串的长度就是2，即dp[i]=2。
- i+1<j，表示i和j之间还有其他字符，我们需要求出区间【i+1,j-1】的最长回文子序列的长度，然后再在前面和后面分别拼上s[i]和s[j]即可。所以dp[i]=dp[i+1][j-1]+2。
如果s[i]!=s[j]：
从整体上来看这整个区间【i-j】，【i-j】的回文子序列包含两部分：
【i,j-1】的回文子序列和【i+1,j】的子序列。所以dp[i][j]=max(dp[i][j-1],dp[i+1][j])。
初始化dp表示：
只需关心dp[i][j]=max(dp[i][j-1],dp[i+1][j])这个表达式中的每一项是否会越界。
前提条件还是i<j，也就是我们只会用到dp表主对角线的右上部分。
而dp[i][j]的更新会用到左边和下边的值：
可以发现，这两个位置其实是主对角线上的元素，满足i==j，而这种情况我们在前面已经判断过了，所以不需要初始化。
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n=s.size();
//i-j区间的最长回文子序列
vector<vector<int>> dp(n,vector<int>(n,0));
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]=1;
else if(i+1==j)
dp[i][j]=2;
else
dp[i][j]=dp[i+1][j-1]+2;
}
else
{
dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
}
}
return dp[0][n-1];
}
};