题目链接：leetcode 647
1.题目
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
2.示例
1）示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
2）示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
3）提示：
1 <= s.length <= 1000
s 由小写英文字母组成文章来源：https://www.toymoban.com/news/detail-447133.html
3.分析
可以看出这是一道区间dp的问题，可以枚举区间的长度为i，区间起点为j，那么区间[j,j+i-1]为回文串当且仅当[j+1,j+i-2]为回文串，可以进行递推操作文章来源地址https://www.toymoban.com/news/detail-447133.html
4.代码
class Solution {
public:
int countSubstrings(string s) {
int f[1010][1010],ans=0;
memset(f,0,sizeof(f));
for(int i=0;i<s.size();i++)
f[i][1]=1;
for(int i=0;i+1<s.size();i++)
if(s[i]==s[i+1])
f[i][2]=1;
for(int i=3;i<=s.size();i++)
for(int j=0;j+i-1<s.size();j++)
if(s[j]==s[j+i-1]&&f[j+1][i-2]!=0)
f[j][i]=1;
for(int i=1;i<=s.size();i++)
for(int j=0;j+i-1<s.size();j++)
ans+=f[j][i];
return ans;
}
};
到了这里，关于leetcode 647. 回文子串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
