给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:
1
2
3
| 输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".
|
示例 2:
1
2
3
| 输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
|
思路：
动态规划：考虑已知前i长度的字符串的回文子串的个数，加一个数之后如何判断，具体看代码。
代码：
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
| class Solution {
public int countSubstrings(String s) {
if(s==null||s.length()<=0){
return 0;
}
int len = s.length();
int [] re = new int[len];
re[0]=1;
for(int i =1;i<len;i++){
int count =1;
char c=s.charAt(i);
for(int j=0;j<i;j++){
if(s.charAt(j)==c && isTrue(s.substring(j,i+1))){
count++;
}
}
re[i]=re[i-1]+count;
}
return re[len-1];
}
public boolean isTrue(String s){
int length = s.length();
int start=0;
int end=length -1;
while(start<=end){
if(s.charAt(start)==s.charAt(end)){
start++;
end--;
}else{
return false;
}
}
return true;
}
}
|