1.题目解析
题目解析:647.回文子串——力扣
测试用例
2.算法原理
1.状态表示
本题需要判断一段字符串是否为回文子串,因此最简单的方法就是保存起开始位置与结束位置,那么就需要一个二维的dp表来保存一段字符串是否为回文子串,dp表的数据类型为bool类型
dp[i][j]:以第i个位置开始,第j个位置结束的字符串是否为回文子串,是则为true,反之为false
2.状态转移方程
由于回文子串需要中心对称,因此判断完两端则需要向中间判断,也就是dp[i][j] = dp[i+1][j-1],但是注意单个字符串与两个相同字符串的情况,这两种情况一定为回文子串,所以在判断前想确定此时的i+1<j是否成立,即一定保证要长度大于3,小于3就一定为true
状态转移方程为:if(s[i]==s[j]) dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;
3.初始化
一开始就确定了单个字符与两个连续字符的情况,所以不用初始化
4.填表顺序
因为用到了i+1与j-1位置,根据状态表示的图示可以知道需要从下向上填表也就是i从后向前,j一定大于i小于n
5.返回值
返回dp表中true的个数
3.实战代码
代码解析
class Solution {
public:
int countSubstrings(string s)
{
int n = s.size();
int sum = 0;
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;
}
if(dp[i][j])
{
sum++;
}
}
}
return sum;
}
};
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 动态规划-回文串问题——647.回文子串
发表评论 取消回复