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.
办法1:动静规划法
参考leetcode5 最长回文子串的动静布局：
class Solution { public int countSubstrings(String s) { int ss = s.length(); int result = 0; boolean dp[][] = new boolean[ss][ss]; for(int i=0;i<ss;i++){ for(int j=0;j<=i;j++){ dp[j][i] = (s.charAt(j)==s.charAt(i))&&(i-j<2||dp[j+1][i-1]==true); if(dp[j][i]==true){ result++; } } } return result; }}在这里与leetcode5不同的中央在于第二层循环时要写==，因为单个字符也是一个回文子串；leetcode5不须要写是因为最长回文字串默认最小就是1.
办法2:两头扩大法
中心点扩大法分为1个中心点和2个中心点，因为1个中心点对应的是奇数长度的字符串，2个中心点对应的是偶数长度的字符串。1个中心点共有字符串长度len个，2个中心点共有字符串长度len-1个，所以共有中心点2len-1个。
class Solution { public int countSubstrings(String s) { int ss = s.length(); int result = 0; for(int i=0;i<2*ss-1;i++){ int left = i/2; int right = left+i%2; while(left>=0&&right<ss&&s.charAt(left)==s.charAt(right)){ result++; left--; right++; } } return result; }}同理此办法也能够用于leetcode5
class Solution { public String longestPalindrome(String s) { int ss = s.length(); int len = 0; String result=""; for(int i=0;i<2*ss-1;i++){ int left = i/2; int right = left+i%2; while(left>=0&&right<ss&&s.charAt(left)==s.charAt(right)){ if(right-left+1>len){ len = right-left+1; result = s.substring(left,right+1); } left--; right++; } } return result; }}