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