共计 910 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:
输入: “abc” 输出: 3 解释: 三个回文子串: “a”, “b”, “c”. 示例 2:
输入: “aaa” 输出: 6 说明: 6 个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”. 注意:
输入的字符串长度不会超过 1000。
解答：这一题可以用穷举法，检查 s[i…j] 是否为回文字串但是应该会超时。不过我们可以这么想，如果现在知道了 s[i…j] 是回文字串，那么如果 s[i-1] == s[j+1]，那么 s[i-1…j+1] 也一定是回文字串。这样就联想到了动态规划。设置 dp[i] [j] 表示 s[i…j] 是否是回文字串，若是为 true，否则为 false。那么对任意的 dp[i] [j] = dp[i+1] [j-1]&&s[i]==s[j]。一旦为 true 就把结果 +1。不过需要注意的是要使用上述的递推公式，需要先求出所有长度为 1 和为 2 的回文字串，这个比较简单，就不赘述了。java ac 代码：
class Solution {
public int countSubstrings(String s) {
//dp[i][j] 表示 s[i…j] 是否为回文字串。
boolean[][] dp = new boolean[s.length()][s.length()];
int ans = 0;
for(int i = 0;i < dp.length;i++)
{
dp[i][i] = true;
ans++;
}
for(int i = 1;i < dp.length;i++)
if(s.charAt(i-1) == s.charAt(i))
{
dp[i-1][i] = true;
ans++;
}
for(int k = 2;k < s.length();k++)
for(int i = k;i < s.length();i++)
if(s.charAt(i-k) == s.charAt(i)&&dp[i-k+1][i-1])
{
dp[i-k][i] = true;
ans++;
}
return ans;
}
}
