647. Palindromic Substrings

算法
动态规划 
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".

这个题目是求回文子序列的个数。最容易想到的是用两个循环的得到所有的子序列，分别用reverse()来验证是否是回文字符串，果然又超时了。这种有动态规划标签的题目永远不能用暴力的方法来做。
通常，求回文字符串的方法是依次比较第一个和最后一个字符，第二个和倒数第二个字符…
所以我们用一个矩阵 $dp[i][j]$ 来表示从i到j的子序列是否是一个回文序列，可以得到递归公式:

即当第一个和最后一个字符相等，切中间的序列也是回文字符串。当字符串长度小于3的时候，只用判断两边的就可以了。 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var countSubstrings = function(s) {
        var count = 0
        var dp = []
        for(let i=0; i<s.length+1; i++) {
            dp[i] = []
            for (let j = 0; j < s.length+1;j++) {
                dp[i][j] = 0
            }
        }
 
        var len = s.length
        for(let i=len-1; i>=0; i--){
            for(let j=i; j<len; j++){
                dp[i][j] = (dp[i+1][j-1] || j-i<3) && (s[i]==s[j])
 
                if(dp[i][j]){
                    count++
                }
            }
        }
 
        return count
 
    };