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.
思路
动态规划问题，也可以用循环验证的方法求解。
方法 & 代码
方法1
很直观的增长回文的方法，循环穷举查找。
class Solution {
/* very intuitive no-DP solution, with extendPalindromic considering odd and even str.
int count = 0;
public int countSubstrings(String s) {
if(s==null||s.length()==0) return 0;
for(int i=0;i<s.length();i++){
extendPalindromic(s,i,i);
extendPalindromic(s,i,i+1);
}
return count;
}
public void extendPalindromic(String s, int left, int right){
while(left>=0 && right < s.length() && s.charAt(left)==s.charAt(right)){
count++;left--;right++;
}
}
}
方法2
DP方法：判断方法那一行写的很漂亮。
class Solution {
public int countSubstrings(String s){
int n = s.length();
int res = 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 <3 || dp[i+1][j-1]);
if(dp[i][j]) res++;
}
}
return res;
}
}
