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.要求回文子串的个数。
这道题和最长回文子串问题其实是一样的，对最长回文子串的解稍做修改即可：
解法一：dp
//dp: based on 最长回文子串 public int countSubstrings(String s) { int length = s.length(); if(length==0) return 0; int res = 0; int[][] dp = new int[length][length]; for(int j = 0;j<length;j++){//列 for(int i = j;i>=0;i--){//每一列从下往上算 if(s.charAt(i)==s.charAt(j) && (j-i<3 || dp[i+1][j-1]==1)){ //j-i<3的使用可以避免单独初始化的工作 //如果str[i]==str[j]且j-i<3意味着： //情形一：a 情形二： aa 情形三 a?a 三种情形都是回文 dp[i][j] = 1;// res++; } else{//str[i]!=str[j], 则一定不是回文, dp[i][j]=0 dp[i][j] = 0; } } } return res; }解法二：中心扩展
//中心扩展 public int countSubstrings(String str) { if(str.length()==0){ return 0; } int count = 0; for(int i = 0;i<str.length();i++){//i==str.length()-1时偶数回文count为0 //从各个位置开始,发现了palindrome(不论奇数还是偶数)都是不会同一个的: //奇数和偶数的回文子串肯定不会是同一个:长度都不一样 //同样是奇数或者偶数，中心位置不一样，那肯定不是同一个回文子串 count += countPalindrome(str,i,i); count += countPalindrome(str,i,i+1); } return count; } private int countPalindrome(String str,int s,int e){ int count = 0; while(s>=0 && e<str.length() && str.charAt(s)==str.charAt(e)){ count++; s--; e++; } return count; }
