Q:

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: “abc” 输出: 3 解释: 三个回文子串: “a”, “b”, “c”. 示例 2:

输入: “aaa” 输出: 6 说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”. 注意:

输入的字符串长度不会超过1000。

A:

中心扩展：

class Solution { public: int countSubstrings(string s) { int siz=s.size(); int res=0; for(int i=0;i<siz;++i) { int m=i,n=i; int j=i,k=i+1; while(m>=0 and j<siz and s[m]==s[j]) { ++res; --m,++j; } while(n>=0 and k<siz and s[n]==s[k]) { ++res,--n,++k; } } return res; } };

DP:

class Solution { public: int countSubstrings(string s) { int siz=s.size(); int res=0; vector<vector<int>> dp(siz,vector<int>(siz,0)); for(int i=0;i<siz;++i) { dp[i][i]=1; ++res; if(i<siz-1 and s[i]==s[i+1]) { dp[i][i+1]=1; ++res; } } for(int i=siz-1;i>=0;--i) //i=siz-1即最后一行不会执行的 { for(int j=i+2;j<siz;++j) { dp[i][j]=(dp[i+1][j-1] and s[i]==s[j])?1:0; res+=dp[i][j]; } } return res; } };