leetcode(力扣) 647. 回文子串（中心扩散法）（动态规划）

题目在这​​：https://leetcode-cn.com/problems/palindromic-substrings/submissions/​​

法一:(中心扩散发)

比如 ：cbabf 选取a为中心点，向两边扩散一次 ，变为 bab，b = b,显然bab为回文子串。继续扩散为 显然 c != f 。cbabf不为回文串。

中心点选择:

可以选择每一个字母作为中心点然后向两边扩散。

但发现一个问题，比如串 ababcf 。无论中心点为何都无法遍历到abab这个子串。但如果中心点并不是一个点，是两个点，选择ba为中心点，向两边扩散即可遍历到abab子串。

所以 ababcf所选择的中心点。a,b,a,b,c,f,ab,ba,ab,bc

三个中心点可由1个中心点扩展一次得到(两边扩展一次，扩展俩字母)。

四个中心点可由2个中心点扩展一次得到。

所以只需要考虑一个和两个中心点即可。

左边右边范围 0和len(arr)-1

完整代码

class Solution:
    def countSubstrings(self, s: str) -> int:
        
        res = 0
        # 单中心点的情况
        for i in range(1,len(s)-1):
            left = i-1
            right = i+1
            while left >= 0 and right <= len(s)-1:
                if s[left] == s[right]:
                    res += 1
                    left -=1
                    right +=1
                else:
                    break
        # 双中心点的情况
        for j in range(len(s)-1):
            left = j
            right = j+1
            while left >= 0 and right <= len(s)-1  and s[left] == s[right]:

                res += 1
                left -= 1
                right += 1

        print(res+len(s))
        return res+len(s)      

、

法二：

动态规划法来做这道题。

1.定义dp数组含义：

定义布尔类型二维数组。dp[i][j] 表示从字符串i到字符串j是否为回文子串。

2.确定状态转移公式：

当s[i] != s[j] 时，显然，不是回文串，直接False

当s[i] == s[j] 时,有三种情况:

• 如果 下标 i == j 则是回文字符串，比如 a本身
• 如果 下表 i和j之间的下表差值为1. 则是回文字符串，比如aa。
• 如果 下表i和j之间的差值大于1，则要看中间的字符串是否回文， 比如 abba， 中间字符串为bb是回文的 ，所以此时也是回文的。如果是 abca ，则显然 bc不是回文的，所以此时也是非回文字符串。 而在dp数组中，dp[i-1][j+1]记录着中间的字符串是否回文。

所以转移公式就很明了了。

3.确定遍历顺序和初始化状态。

显然数组初始化为全部False。

而遍历顺序需要注意。

因为我们当前dp[i][j]的情况取决于dp[i-1][j+1] 的情况。想象一下二维数组里这俩的位置。显然是从左下到右上。

看这个图。

要从左下角开始填数字，所以要倒着遍历。

在这里插入代码片class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False for i in range(len(s))] for j in range(len(s))]
        print(dp)
        res = 0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if j-i <=1:
                        dp[i][j] = True
                        res += 1
                    elif dp[i+1][j-1]:
                        res +=1
                        dp[i][j] = True
        print(res)
        return