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;
}
}