Leetcode 647. 回文子串
题目链接：647 回文子串
题干：给你一个字符串
s，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
思考一：动态规划。本题考虑dp数组含义的思路与以往不同。
- 确定dp数组（dp table）以及下标的含义
大多数题目是按题目求什么来定义dp数组，但本题如果dp数组定义为，dp[i] ：下标i结尾的字符串含回文串的个数，很难找到递归关系。dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。
因此要看回文串的性质。 如图：
可以看出在判断字符串S是否是回文时，如果知道 s[1，3]子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，字符串s 就是回文串。
此时就找到一种递归关系，也就是判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j - 1]）） 是否是回文。
为了明确这种递归关系，dp数组是要定义成一位二维dp数组。布尔类型的dp[i][j]：区间[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
- 确定递推公式
在确定递推公式时，就要分析两种情况，分别是s[i]与s[j]相等与不相等。
当s[i]与s[j]不相等，当前处理的子串一定不是回文，因此dp[i][j] = false。
当s[i]与s[j]相等时，有如下三种情况
- 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
- 情况二：下标i 与 j相差为1，两相同字符例如aa，也是回文子串
- 情况三：下标i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]相同，那么考虑缩小处理区间的内部情况，即区间[i+1, j-1]的aba，再这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
再用result来记录回文子串的数量。
- dp数组如何初始化
从递推公式可以看出dp[i][j]全初始化为false，才不影响回文子串判断。
- 确定遍历顺序
从递推公式可以看出，情况三是根据dp[i + 1][j - 1]是否为true来判断对dp[i][j]的赋值。因此一定要从下到上，从左到右遍历，才能保证dp[i][j]的正确赋值。
此外从dp数组的定义可以看出，区间尾部 j 一定是大于等于区间首部 i 的，因此内部循环区间尾部 j 要从 i 开始遍历。
- 举例推导dp数组
举例："aaa"，dp[i][j]状态如下：
图中有6个true，所以就是有6个回文子串。
代码：
class Solution {
public:
int countSubstrings(string s) {
//dp[i][j]:区间[i, j]的子串是否为回文(true-是， false-否)
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
int result = 0; //记录回文子串数量
for (int i = s.size() - 1; i >= 0; i--) { //遍历区间头部
for (int j = i; j < s.size(); j++) { //遍历区间尾部
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
//情况一：同一字符 情况二：两相同字符 情况三：首尾缩小的子串是为回文
result++;
dp[i][j] = true;
}
}
}
return result;
}
};思考二：双指针法。确定回文串就是找中心然后向两边扩散看是不是对称的。
在遍历中心点的时候，要注意中心点有以下两种情况：
- 一个元素作为作为中心点
- 两个元素也可以作为中心点
超过三个元素的情况都可以从情况一和情况二推出。
遍历字符串时可以分别处理这两种情况，并将返回值相加到result。
代码：
class Solution {
public:
int countSubstrings(string s) {
int result = 0;
for (int i = 0; i < s.size(); i++) { //遍历字符串s
result += manacherNum(s, i, i); //以i为中心
result += manacherNum(s, i, i + 1); //以i和i + 1为中心
}
return result;
}
//获取回文子串数目
int manacherNum(const string& s, int head, int rear) {
int res = 0;
while (head >= 0 && rear < s.size() && s[head] == s[rear]) {
res++;
//扩大处理范围
head--;
rear++;
}
return res;
}
};Leetcode 5.最长回文子串
题目链接：5 最长回文子串
题干：给你一个字符串
s，找到s中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
思考一：动态规划。
- 确定dp数组（dp table）以及下标的含义
dp[i] ：区间[i, j]的子串中最长回文子串的长度
- 确定递推公式
在确定递推公式时，就要分析两种情况，分别是s[i]与s[j]相等与不相等。
当s[i]与s[j]不相等，当前处理的子串一定不是回文，因此dp[i][j] = 0;
当s[i]与s[j]相等时，有如下三种情况
- 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串，因此dp[i][j] = 1；
- 情况二：下标i 与 j相差为1，两相同字符例如aa，也是回文子串，因此dp[i][j] = 2；
- 情况三：下标i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]相同，那么考虑缩小处理区间的内部情况，即区间[i+1, j-1]的aba，若这个区间仍为回文（即dp[i + 1][j - 1] = j - i - 1)，则dp[i][j] = dp[i + 1][j - 1] + 2;
同时用result记录最大回文子串的起始下标及其长度。并在遍历过程中比较更新记录值。
另外情况二和情况三可统一处理，具体理由在下面初始化介绍。
- dp数组如何初始化
从递推公式可以看出，情况一可提前处理，即使dp[i][i] = 1；而对于其余元素dp[i][j]应初始化为0。
此时对于情况二，dp[i][j] = 0 = j - i - 1。因此情况二和情况三可统一处理。
- 确定遍历顺序
从递推公式可以看出，情况三是根据dp[i + 1][j - 1]来判断对dp[i][j]的赋值。因此一定要从下到上，从左到右遍历，才能保证dp[i][j]的正确赋值。
此外从dp数组的定义以及dp数组的初始化可以看出，区间尾部 j 一定是大于等于区间首部 i 的，并且区间尾部 j 和区间首部 i 相同的情况提前处理过，因此内部循环区间尾部 j 要从 i + 1 开始遍历。
- 举例推导dp数组
举例："babad"，dp[i][j]状态如下：
返回首个记录的最大回文子串，则返回子串区间[1, 3]，即aba.
代码：
class Solution {
public:
string longestPalindrome(string s) {
//dp[i][j]:区间[i, j]的子串中最长回文子串的长度
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
pair<int, int> result(0, 1); //记录最长回文子串起始下标及其长度
for (int i = 0; i < s.size(); i++) //区间长度为1则回文子序列长度也为1
dp[i][i] = 1;
for (int i = s.size() - 2; i >= 0; i--) { //遍历区间头部
for (int j = i + 1; j < s.size(); j++) { //遍历区间尾部
if (s[i] == s[j] && dp[i + 1][j - 1] == j - i - 1) {
//字符相同 且 去头去尾子区间dp[i + 1][j - 1]值同区间长度相同
dp[i][j] = dp[i + 1][j - 1] + 2;
if (dp[i][j] > result.second) {
//更新记录
result.first = i;
result.second = j - i + 1;
}
}
}
}
return s.substr(result.first, result.second);
}
};思考二：双指针法。本题和上题相似，唯一的区别在于上题是统计回文子串数量，本题是求最长回文子串长度。但都可以通过遍历所有回文子串来处理。
本题在处理时将得到的最长回文子序列和记录值进行比较，若长度大于记录值则更新记录值。当然由于本题返回的是字符串，因此除了记录最长回文子串长度之外还得记录起始下标。
代码：
class Solution {
public:
string longestPalindrome(string s) {
pair<int, int> result(0, 0); //记录最大回文子串起始下标及其长度
for (int i = 0; i < s.size(); i++) {
manacherMax(s, result, i, i); //以i为中心
manacherMax(s, result, i, i + 1); //以i和i + 1为中心
}
return s.substr(result.first, result.second);
}
void manacherMax(const string& s, pair<int, int>& result, int i, int j) {
int num = i == j ? - 1 : 0; //记录当前中心的最大回文子串长度
while (i >= 0 && j < s.size() && s[i] == s[j]) {
num += 2; //更新回文子串长度
//扩大处理区间
i--;
j++;
}
if (num > result.second) {
//更新记录信息
result.second = num;
result.first = i + 1;
}
}
};Leetcode 516.最长回文子序列
题目链接：516 最长回文子序列
题干：给你一个字符串
s，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
思考：动态规划。本题和上题唯一的区别：前者求最大回文子串，后者求最大回文子序列。在动态规划五部曲里仅在 确定递推公式 存在差异。
在确定递推公式时，仍要分析s[i]与s[j]相等与不相等两种情况。
- 当s[i]与s[j]相等时，当前处理的子串一定存在回文子序列，因此dp[i][j] = dp[i + 1][j - 1] + 2;
- 当s[i]与s[j]不相等时，则考虑去头去尾区间的子串的回文子序列，因此dp[i][j] = max(dp[i + 1][j], dp[i][j - 1];
但此题不需要result来记录。因为要求的是回文子序列，所以最后的答案返回整个字符串区间中的最大回文子序列即可（即dp[0][s.size() - 1]）
代码：
class Solution {
public:
int longestPalindromeSubseq(string s) {
//dp[i][j]:区间[i, j]的子串中最长回文子序列的长度
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) //区间长度为1则回文子序列长度也为1
dp[i][i] = 1;
for (int i = s.size() - 2; i >= 0; i--) { //遍历区间头部
for (int j = i + 1; j < s.size(); j++) { //遍历区间尾部
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2; //字符相同则取去头去尾子区间长度加2
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); //去头或去尾子区间长度较大值
}
}
return dp[0][s.size() - 1];
}
};动态规划专题总结：
- 首先便是最重要的动规五部曲，分别为：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
- 此外对于背包问题系列、打家劫舍系列、股票系列、子序列系列之前有简单总结，这里附上网上大佬的总结图。
