潮汕17网站一起做网店官网自媒体seo优化

647. 回文子串

给你一个字符串 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;}
};