给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
分析：本题有两种方法，相对来说，中心扩散法容易想，也更快更便捷，动态规划法也还行，两种方法都要掌握
方法一：动态规划：
用动态规划做我们就要想明白dp数组怎么建，含义是啥。
回文子串，那么要有首尾进行判断，必须建立二维dp数组，dp[i][j]在本题中可以表示为boolean型变量，意思是以i为首，j为尾的字符串是否为dp数组。
如何得到？首先要判断i和j的字符是否相等，不相等那么一定不是
相等后，要思考，有三种情况：
i和j表示的是一个数，那么不需要别的判断，为true；
i和j表示的是相邻的两个数，那么也可以，为true；
i和j中间还有其他数，这时候就需要dp数组进行推导了，即需要判断dp[i+1][j-1]是否为true，是的话dp[i][j]也为true；
初始化，所有的都要初始化为false；
遍历顺序？本题在遍历顺序上也有讲究，从递推公式中可以看出，dp[i][j]的推导需要dp[i+1][j-1]的值，那么dp[i+1][j-1]就需要在dp[i][j]之前进行判断。i表示行数，j表示列数，我们需要自下向上，自左至右，同时由于我们设定i为头，j为尾，那么在二维dp数组中我们需要填入的是右上的三角块的值。
参考代码：
public int countSubstrings(String s) {
int ret=0;
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i=s.length()-1;i>=0;i—){
for(int j=i;j
if(j-i<=1){
ret++;dp[i][j]=true;
}else if(dp[i+1][j-1]==true){
dp[i][j]=true;ret++;
}
}
}
}
return ret;
}
方法二：中心扩散法
这个方法更容易理解，效率也更高，此题推荐这种解法；
所谓中心扩散法，即以将一个字符或两个字符为中心，不断外扩，需要首尾两个指针，比较两个指针判断值是否相等，相等的话，结果+1，并继续外扩；
需要一个或两个字符为中心，因为aba这种三个字符被包含在了一个字符的情况，而一个字符的情况不包含aa这种情况，所以需要一个或两个字符为中心，这样代码的设置也会十分巧妙。
参考代码：
public int countSubstrings(String s) {
int ret=0;
int left=0,right=0;
for(int i=0;i
right=left+i%2;
while(left>=0&&right
left—;
right++;
}
}
return ret;
}
若有收获，就点个赞吧
0 人点赞
