DP算法：
①單個字符是回文；
②兩個連續字符，如果相等則是回文；
③3個以上的字符，兩頭相等且去掉首尾后依然是回文。

以 s=‘aba’為例：

[0][0]	[0][1]	[0][2]
[1][0]	[1][1]	[1][2]
[2][0]	[2][1]	[2][2]

i = 0：dp[0][0]，‘a’

i = 1：dp[0][1]，‘ab’
i = 1：dp[1][1]，‘b’

i = 2：dp[0][2]，‘aba’
i = 2：dp[1][2]，‘ba’
i = 2：dp[2][2]，‘a’

class Solution(object):def countSubstrings(self, s):""":type s: str:rtype: int"""n = len(s)dp = [[0]*n for x in range(n)]count = 0for i in range(n):for j in range(i):dp[j][i] = (s[i]==s[j]) & ((i-j==1) | dp[j+1][i-1])if dp[j][i]:count += 1dp[i][i] = 1count += 1return count

總結

以上是生活随笔為你收集整理的31/100. Palindromic Substrings的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。