回文子串

2025/10/16

思路：动态规划

num[i] = num[i - 1] + 1 +if(i-1~i是不是回文) + … + if(1~i是不是回文)

评价：一维DP不常见吧，这样相当于暴力求解？

推荐做法：两头是不固定的，而且回文串所以是二维DP。很奇怪，仔细看看。

2025/10/19

def countSubstrings(self, s: str) -> int:
        
        count = 0
        for k in range(0, s):
            for i in range(len(s)):
                if k == 0:
                    isPa[i][i+k] = true
                elif k == 1:
                    isPa[i][i+k] = (s[i] == s[i+k])
                else: 
                    isPa[i][i+k] = isPa[i+1][i+k-1] if s[i-1]==s[i+k-1] else false
                
                if isPa[i][i+k] == true: 
                    count +=1 
        return count