一、题目
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
https://leetcode.cn/problems/palindromic-substrings/description/
二、算法思路
本题和 最长回文子串（动态规划）类似，使用动态规划方法解决。
1、定义状态：
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示区间
[
i
,
j
]
[i,j]
[i,j] 是否为回文子串，如果是，
d
p
[
i
]
[
j
]
=
t
r
u
e
dp[i][j]=true
dp[i][j]=true，否则为
f
a
l
s
e
false
false。
2、初始化状态：单个字符是回文子串，
d
p
[
i
]
[
i
]
=
t
r
u
e
dp[i][i]=true
dp[i][i]=true。
3、状态转移：枚举区间长度，从小到大计算
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的值，具体的转移方程为：
dp[i][j] = true, i == j
s[i] == s[j], j = i + 1
s[i] == s[j] && dp[i+1][j-1], j > i + 1
回文子串的长度可以是 1 或 2，因此先将所有长度为 1 或 2 的子串作为回文子串进行初始化。
然后，从长度为 3 开始枚举所有可能的回文子串，通过状态转移方程dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) 计算出 dp[i][j] 的值。
最后统计回文子串的个数。
三、代码实现
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int ans = 0;
boolean[][] dp = new boolean[n][n];
// 枚举回文子串的长度，从 1 到 n
for (int len = 1; len <= n; len++) {
// 枚举回文子串的起始位置 i，结束位置 j
for (int i = 0; i < n; i++) {
int j = i + len - 1; //回文子串右边界位置
if (j >= n) { //右边界位置超过字符串长度跳出循环
break;
}
if (len == 1) {
dp[i][j] = true;
} else if (len == 2) {
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]);
}
if (dp[i][j]) { //统计回文子串个数
ans++;
}
}
}
return ans;
}
}
四、复杂度分析
- 时间复杂度为
O
(
n
2
)
O(n^2)
O(n2) - 空间复杂度:
O
(
n
2
)
O(n^2)
O(n2)