05 August 2008
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
要求返回所有子回文子串的数量，可以按照奇偶来计算；也可以利用DP的办法（https://leetcode.com/problems/palindromic-substrings/discuss/105707/Java-DP-solution-based-on-longest-palindromic-substring）
中心扩展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution6472 {
public int countSubstrings(String s) {
// 中心扩展法
int result = 0;
for (int center = 0; center < 2 * s.length() - 1; center++) {
// left和right指针和中心点的关系是？
// 首先是left，有一个很明显的2倍关系的存在，其次是right，可能和left指向同一个（偶数时），也可能往后移动一个（奇数）
// 大致的关系出来了，可以选择带两个特殊例子进去看看是否满足。
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
result++;
left--;
right++;
}
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
int count = 0;
public int countSubstrings(String s) {
if (s.isEmpty()) {
return 0;
}
for (int i = 0; i < s.length(); i++) {
countSubstrings(s, i, i);//以当前字符自己为中心，奇数
countSubstrings(s, i, i + 1);//以当前和后面的字符为中心，偶数
}
return count;
}
private void countSubstrings(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
}
}
DP & Manacher