【算法训练营day57】LeetCode647. 回文子串 LeetCode516. 最长回文子序列
2023-04-18 15:19:13 时间
LeetCode647. 回文子串
题目链接:647. 回文子串
独上高楼,望尽天涯路
直接看题解。
慕然回首,灯火阑珊处
首先是确定dp数组以及下标的含义。
布尔类型的
dp[i][j]
:表示区间范围[i,j](注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]
为true,否则为false。
其次是递推公式。
在确定递推公式时,就要分析如下几种情况。
整体上是两种,就是s[i]与s[j]相等,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到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是i+1与j-1区间,这个区间是不是回文就看
dp[i + 1][j - 1]
是否为true。
最后是遍历顺序。
遍历顺序可有有点讲究了。
首先从递推公式中可以看出,情况三是根据
dp[i + 1][j - 1]
是否为true,在对dp[i][j]
进行赋值true的。
dp[i + 1][j - 1]
在dp[i][j]
的左下角,如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的dp[i + 1][j - 1]
,也就是根据不确定是不是回文的区间[i+1, j-1],来判断了[i, j]是不是回文,那结果一定是不对的。所以一定要从下到上,从左到右遍历,这样保证
dp[i + 1][j - 1]
都是经过计算的。
class Solution {
public:
int countSubstrings(string s) {
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]) {
if (j - i <= 1) {
result++;
dp[i][j] = true;
}
else if (dp[i + 1][j - 1]) {
result++;
dp[i][j] = true;
}
}
}
}
return result;
}
};
LeetCode516. 最长回文子序列
题目链接:516. 最长回文子序列
独上高楼,望尽天涯路
动态规划,完结撒花!
慕然回首,灯火阑珊处
和上一道题很相似,需要多考虑的一点是当s[i]不等于s[j]的时候的递推公式。
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i] == s[j]) {
if (j - i <= 1) {
dp[i][j] = j - i + 1;
}
else {
dp[i][j] = dp[i + 1][j - 1] + 2;
}
}
else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); // 重点关注
}
}
}
return dp[0][s.size() - 1];
}
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击