题目
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
解题
方法一：动态规划
class Solution { public: int countSubstrings(string s) { vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false)); int res=0; for(int l=0;l<s.size();l++){ for(int i=0;i<s.size();i++){ int j=i+l; if(j>=s.size()) break; if(l==0){ res++; dp[i][j]=true; } else if(l==1&&s[i]==s[j]){ res++; dp[i][j]=true; } else if(l>=2&&s[i]==s[j]&&dp[i+1][j-1]){ res++; dp[i][j]=true; } } } return res; } };
注意一定要先遍历长度 l
而不能是i和j
假如s=”aaa“
当i=0,j=2时候 对应就是字符串”aaa“
应该是回文串，但是dp[i+1][j-1]此时还是false，因为还没遍历过。
因此要先遍历长度，再遍历i
下面的代码就是错误的。（遍历方式不对）
class Solution { public: int countSubstrings(string s) { int n=s.size(); vector<vector<bool>> dp(n,vector<bool>(n,false)); int res=0; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(i==j){ dp[i][j]=true; res++; } else if(j-i==1&&s[i]==s[j]){ dp[i][j]=true; res++; } else if((s[i]==s[j])&&dp[i+1][j-1]){ dp[i][j]=true; res++; } } } return res; } };
