问题
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串
示例 1:
输入:"abc"
输出:3
解释:三个回文子串: “a”, “b”, “c”
示例 2:
输入:"aaa"
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
动态规划
动规五部曲:
确定dp数组以及下标的含义
- 布尔类型的
dp[i][j]
:表示区间范围[i,j]
(注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]
为true
,否则为false
- 布尔类型的
确定递推公式
- 在确定递推公式时,就要分析如下几种情况
- 整体上是两种,就是
s[i]
与s[j]
相等,s[i]
与s[j]
不相等这两种- 当
s[i]
与s[j]
不相等,那没啥好说的了,dp[i][j]
一定是false
- 当
s[i]
与s[j]
相等时,这就复杂一些了,有如下三种情况- 情况一:下标
i
与j
相同,同一个字符例如a
,当然是回文子串 - 情况二:下标
i
与j
相差为1
,例如aa
,也是文子串 - 情况三:下标:
i
与j
相差大于1
的时候,例如cabac
,此时s[i]
与s[j]
已经相同了,我们看i
到j
区间是不是回文子串就看aba
是不是回文就可以了,那么aba
的区间就是i+1
与j-1
区间,这个区间是不是回文就看dp[i + 1][j - 1]
是否为true
result就是统计回文子串的数量if (s[i] == s[j]) {
if (j - i <= 1) { // 情况一 和 情况二
result++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { // 情况三
result++;
dp[i][j] = true;
}
}
注意这里我没有列出当s[i]
与s[j]
不相等的时候,因为在下面dp[i][j]
初始化的时候,就初始为false
- 情况一:下标
- 当
- 整体上是两种,就是
- 在确定递推公式时,就要分析如下几种情况
dp数组如何初始化
dp[i][j]
可以初始化为true
么?当然不行,怎能刚开始就全都匹配上了,所以dp[i][j]
初始化为false
确定遍历顺序
- 遍历顺序可有有点讲究了
- 首先从递推公式中可以看出,情况三是根据
dp[i + 1][j - 1]
是否为true
,在对dp[i][j]
进行赋值true
的,dp[i + 1][j - 1]
在dp[i][j]
的左下角
- 如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的
dp[i + 1][j - 1]
,也就是根据不确定是不是回文的区间[i+1,j-1]
,来判断了[i,j]
是不是回文,那结果一定是不对的 - 所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的
for (int i = s.length() - 1; i >= 0; i--) { // 注意遍历顺序
for (int j = i; j < s.length(); j++) {
if (s[i] == s[j]) {
if (j - i <= 1) { // 情况一 和 情况二
result++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { // 情况三
result++;
dp[i][j] = true;
}
}
}
}
- 举例推导dp数组
- 举例,输入:”aaa”,dp[i][j]状态如下:
- 举例,输入:”aaa”,dp[i][j]状态如下:
图中有6个true,所以就是有6个回文子串。
注意因为dp[i][j]的定义,所以j一定是大于等于i的,那么在填充dp[i][j]的时候一定是只填充右上半部分
class Solution {
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int result = 0;
for (int i = s.length() - 1; i >= 0; i--) { // 注意遍历顺序
for (int j = i; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i <= 1) { // 情况一 和 情况二
result++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { // 情况三
result++;
dp[i][j] = true;
}
}
}
}
return result;
}
}
简洁如下:
class Solution {
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int result = 0;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
result++;
dp[i][j] = true;
}
}
}
return result;
}
}
- 时间复杂度:
-
双指针法
动态规划的空间复杂度是偏高的,我们再看一下双指针法。
首先确定回文串,就是找中心然后向两边扩散看是不是对称的就可以了
在遍历中心点的时候,要注意中心点有两种情况 一个元素可以作为中心点
- 两个元素也可以作为中心点
这两种情况可以放在一起计算,但分别计算思路更清晰,我倾向于分别计算,代码如下:
class Solution {
public int countSubstrings(String s) {
int result = 0;
for (int i = 0; i < s.length(); i++) {
result += extend(s, i, i, s.length()); // 以i为中心
result += extend(s, i, i + 1, s.length()); // 以i和i+1为中心
}
return result;
}
public int extend(String s, int i, int j, int n) {
int res = 0;
while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
i--;
j++;
res++;
}
return res;
}
}
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)