leetcode 647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false
这个状态转移方程是什么意思呢？

当只有一个字符时，比如 a ，s[i] == s[j] && (j - i < 2）自然成立，自然是一个回文串。
当有两个字符时，(j - i < 2）是自然成立的，如果是相等的（s[i] == s[j]），比如 aa，也是一个回文串。
当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s[i]==s[j] 时，自然要看 dp[i+1][j-1] 是不是一个回文串

class Solution(object):
    def countSubstrings(self, s):
        """ :type s: str :rtype: int """
        tot = 0
        n = len(s)
        dp = [[False]*n for i in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if i == j:
                    dp[i][j] = True 
                    tot += 1
                elif (s[i] == s[j]) and (j - i == 1):
                    dp[i][j] = True 
                    tot += 1
                elif (s[i] == s[j]) and (dp[i+1][j-1]):
                    dp[i][j] = True 
                    tot += 1 
        return tot