力扣题解（回文子串）
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
思路：
首先，本题要求的是数目，而且不要求没有重复，因此不同位置可以出现相同的回文子串。
具体做法是以i位置为中心两边扩展，和以i，i+1位置为中心向两边扩展，分别求出符合要求的回文子串数目，然后加合即可。
class Solution {
public:
int countSubstrings(string s) {
int n=s.size();
vector<int>dp(n,1);
if(s[0]==s[1])
dp[0]++;
for(int i=1;i<n-1;i++)
{
int j=1;
while(i-j>=0&&i+j<n&&s[i-j]==s[i+j])
{
dp[i]++;
j++;
}
j=0;
while(i-j>=0&&i+1+j<n&&s[i-j]==s[i+j+1])
{
dp[i]++;
j++;
}
}
int ret=0;
for(auto e:dp)
{
cout<<e;
ret+=e;
}
return ret;
}
};原文地址：https://blog.csdn.net/yyssas/article/details/140401455
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！