剑指offer020-回文子字符串的个数
题目
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s 由小写英文字母组成
注意：本题与主站 647 题相同：https://leetcode-cn.com/problems/palindromic-substrings/
👍 16👎 0
思路
乍一想感觉是动态规划，我们定义dp[i][j]为s的i-j是否回文，这样我们只要统计dp数组中1的个数就好
很明显，对于每一个单个字符来说，s[i]本身就是回文，一个字符的
我们考虑dp[i][j]的递推关系式
dp[i][j]
如果s[i] == s[j]的话，dp[i][j]=dp[i+1][j-1]
如果s[i] == s[j],dp[i][j]=0
我们初始化dp数组
1
2
3
4
5
6
7
| int[][] dp = new int[m][m];
int res = 0;
for (int i = 0; i < m; i++) {
dp[i][i] = 1;
++res;
}
|
递推关系式dp[i][j]=dp[i+1][j-1]是从右上往左下走，因此我们需要从左下到右上填充数据
还考虑到如果只有两个字符，会出现内部字符串为空或者left<right的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| for (int i = m - 1; i >= 0; i--) {
for (int j = i + 1; j < m; j++) {
int left = i + 1;
int right = j - 1;
if (left >= right) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 1;
++res;
}
} else {
if (s.charAt(i) == s.charAt(j) && dp[left][right] == 1) {
dp[i][j] = 1;
++res;
}
}
}
}
|
1
2
3
| 解答成功:
执行耗时:12 ms,击败了21.44% 的Java用户
内存消耗:42.4 MB,击败了5.02% 的Java用户
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public int countSubstrings(String s) {
int m = s.length();
if (m == 1) {
return 1;
}
if (m == 2) {
return 2 + (s.charAt(0) == s.charAt(1) ? 1 : 0);
}
int[][] dp = new int[m][m];
int res = 0;
for (int i = 0; i < m; i++) {
dp[i][i] = 1;
++res;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = i + 1; j < m; j++) {
int left = i + 1;
int right = j - 1;
if (left >= right) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 1;
++res;
}
} else {
if (s.charAt(i) == s.charAt(j) && dp[left][right] == 1) {
dp[i][j] = 1;
++res;
}
}
}
}
return res;
}
}
|