题目地址：

https://www.lintcode.com/problem/palindromic-substrings/description

给定一个字符串$s$，问其有多少回文子串。只要起始点或终止点不同，就视为不同子串。

思路是动态规划。设$f[i][j]$是$s[i:j]$是否是回文串。则当$i=j$时，$f[i][j]$为真；当$i=j-1$时，$f[i][j]$为$s[i]=s[j]$是否为真；否则$f[i][j]$为$s[i]=s[j]$和$f[i+1][j-1]$是否同时为真。接着同时做计数即可。代码如下：

public class Solution { /** * @param str: s string * @return: return an integer, denote the number of the palindromic substrings */ public int countPalindromicSubstrings(String str) { // write your code here int res = 0; boolean[][] dp = new boolean[str.length()][str.length()]; // 枚举子串长度 for (int len = 1; len <= str.length(); len++) { // 枚举左端点 for (int i = 0; i + len - 1 < str.length(); i++) { // 算左右端点 int l = i, r = i + len - 1; if (len == 1) { dp[l][r] = true; } else if (len == 2) { dp[l][r] = str.charAt(l) == str.charAt(r); } else { dp[l][r] = str.charAt(l) == str.charAt(r) && dp[l + 1][r - 1]; } if (dp[l][r]) { res++; } } } return res; } }

时空复杂度$O(l_s^2)$。