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:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Note:
The input string length won’t exceed 1000.
找出字符串s中一共有多少个回文子串，相同的回文子串但是起止index不同也算不同的回文子串。
思路：
(1) DP
只需要记录i 到 j的子串是否是回文子串，遍历所有的子串，如果是子串就给结果+1
判断是否是回文子串：s[i] == s[j]时，如果i = j，指向的是同一字符，那显然是回文子串，如果i 和 j 是邻居，也是回文子串，如果i 和 j中间只隔一个字符，那么i 到 j也是回文子串。
但是，如果间隔的>2，就需要判断dp[i+1][j-1]
注意判断的同时dp[i][j]自己也要更新
public int countSubstrings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int result = 0;
boolean[][] dp = new boolean[n][n];
for(int i = n-1; i >= 0; i--) {
for(int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i <= 2 || dp[i+1][j-1]);
if(dp[i][j]){
result ++;
}
}
}
return result;
}
(2) 左右扩散
遍历每一个字符，以这个字符为中心左右扩散，每扩散一个对称的，就在结果+1。
当然分奇数和偶数的情况，奇数就是i 自己扩散，偶数情况就以i，i+1为中心扩散
class Solution {
int result = 0;
public int countSubstrings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
for(int i = 0; i < n; i++) {
counter(s, i, i, n);
counter(s, i, i+1, n);
}
return result;
}
void counter(String s, int left, int right, int n) {
while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
left --;
right ++;
result ++;
}
}
}