【代码随想录训练营第42期 Day46打卡 - 回文问题 - LeetCode 647. 回文子串 516.最长回文子序列
目录
一、做题心得
二、题目与题解
题目一：647. 回文子串
题目链接
题解1：动态规划
题解2：中心扩展法
题目二：516.最长回文子序列
题目链接
题解1：反转+LCS
题解2：动态规划
三、小结
一、做题心得
今天是动态规划章节的最后内容，做的是回文问题--回文子串和最长回文子序列。对于这一类问题，我们一般采用二维dp进行实现，其中，dp[i][j]中的 i, j 分别表示子串的起始位置和终止位置，然后通过两层循环遍历即可。
这里直接开始今天的内容。
二、题目与题解
题目一：647. 回文子串
题目链接
647. 回文子串 - 力扣（LeetCode）
给你一个字符串
s，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"提示：
1 <= s.length <= 1000s由小写英文字母组成
题解1：动态规划
动态规划是解决各种子序列问题的经典解法。
对于回文子串问题，我们通过设置二维dp数组dp[i][j]，用 i 与 j 分别表示当前子串的起始位置和终止位置。-- 这一道题是得到回文子串的数目，那么我们就可以设置 bool 型的dp数组，从而对于每一个为 true 的子串进行数目上的+1。（注意，在这里：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串）
然后通过两层循环遍历起始位置和终止位置，从而确立当前子串是否为回文串的条件：
s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])这里的含义：s[i]和s[j]相等（当前两端点相等） + 子串长度小于等于2，或者dp[i+1][j-1]为true（即s[i+1,j-1]是回文串）
代码如下：
class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false)); //dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串 -- bool型dp数组
int ans = 0; //统计个数--结果
for (int j = 0; j < n; j++) { //外层循环j表示子串的结束位置，从0到n-1
for (int i = 0; i <= j; i++) { //内层循环i表示子串的开始位置，从0到j
//s[i]和s[j]相等（当前两端点相等） + 子串长度小于等于2，或者dp[i+1][j-1]为true（即s[i+1,j-1]是回文串） -- 这时在区间s[i,j]一定是回文串
if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
};题解2：中心扩展法
在这里，中心扩展法的思想 -- 从中心向外扩展：两个关键--1.主函数考虑s长度为奇数与偶数两种情况（中心是一个位置还是两个）；2.extend()函数从内向外中心扩展，怎样满足是回文子串的条件。
具体如何实现，直接看以下代码（含详细注释）：
class Solution {
public:
int extend(string &s, int i, int j, int n) { //extend()函数用于计算以s[i]和s[j]为中心的回文子串的数量
int t = 0; //统计当前情况的回文子串数：每次调用函数时，从0开始
while(i >= 0 && j < n && s[i] == s[j]) { //关键：中心扩展法--从中心向外扩展，当内层两个字符相同时（不越界），即满足是回文子串
i--; //i向左移动，j向右移动，继续检查下一对字符
j++;
t++; //回文子串数+1
}
return t;
}
int countSubstrings(string s) {
int ans = 0; //统计个数 -- 结果
int n = s.size();
for(int i = 0; i < n; i++) { //遍历字符串的每个字符，以每个字符为中心，检查回文子串
ans += extend(s, i, i, n); //检查以s[i]为中心的奇数长度回文子串的数量
ans += extend(s, i, i+1, n); //检查以s[i]和s[i+1]为中心的偶数长度回文子串的数量
}
return ans;
}
};题目二：516.最长回文子序列
题目链接
516. 最长回文子序列 - 力扣（LeetCode）
给你一个字符串
s，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。提示：
1 <= s.length <= 1000s仅由小写英文字母组成
题解1：反转+LCS
这个思路似乎不太容易想到：原字符串与将其反转后的字符串的最长公共子序列（LCS）就是原字符串的最长回文子序列。
可以通过画图举例探讨以上思路的正确性--其实回文这一特性就可以往反转的角度去思考。
由于最长公共子序列问题之前打卡就有出现，这里就不详细解释了。
代码如下：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
string t = s;
reverse(s.begin(), s.end());
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++){
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][n];
}
};题解2：动态规划
其实从某种程度上来说，思路和最长公共子序列有些像，尤其是对于处理当前对应两字符相同或者不同的情况。
dp数组：dp[i][j]表示字符串s在[i,j]区间内的最长回文子序列的长度 -- i为起始位置, j为终止位置
dp数组初始化：只有一个元素的子串对应着长度为1的子序列
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}状态方程：
1.当s[i] == s[j]时，可以形成一个新的回文子序列，其长度为dp[i+1][j-1] + 2
2.当s[i] != s[j]时，需要取不包含s[i]或s[j]中的最长回文子序列长度，即max(dp[i+1][j], dp[i][j-1])
遍历方式：由状态方程可知，当前 dp[i][j] 与 dp[i + 1][j - 1]有关，那么可以得出，对于dp数组的遍历，我们需要：从下往上，从左往右。
完整代码如下：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0)); //dp[i][j]表示字符串s在[i,j]区间内的最长回文子序列的长度 -- i为起始位置, j为终止位置
for (int i = 0; i < n; i++) { //初始化只有一个元素的子串 -- 长度为1的子序列
dp[i][i] = 1;
}
//填充dp数组，从下往上，从左往右 -- 这里需要注意的是 i 的遍历必须是从下往上（从大到小）：因为当前 dp[i][j] 与 dp[i + 1][j - 1]有关，需要先得出 dp[i + 1]
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
//当s[i] == s[j]时，可以形成一个新的回文子序列，其长度为dp[i+1][j-1] + 2
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
}
//当s[i] != s[j]时，需要取不包含s[i]或s[j]中的最长回文子序列长度，即max(dp[i+1][j], dp[i][j-1])
else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1]; //整个字符串s
}
};三、小结
今天的打卡到此结束，动态规划章节也就此结尾。