回文子串-动态规划647-python

没看答案，双指针+传统判断回文串，用memo储存已经判断过的子串，防止重复判断，时间复杂度O(n^3)。

from collections import defaultdict

class Solution:
    def countSubstrings(self, s: str) -> int:
        memo = defaultdict(bool)
        n = len(s)
        res = 0

        def dfs(s, start, end):
            if (start, end) in memo:
                return memo[(start, end)]
            
            if abs(start - end) <= 1:
                flag = s[start] == s[end]
                memo[(start, end)] = flag
                return flag
            else:
                flag = dfs(s, start+1, end-1) and s[start] == s[end]
                memo[(start, end)] = flag
                return flag
        
        for i in range(n):
            for j in range(i, n):
                if abs(i-j) <= 1:
                    flag = s[i] == s[j]
                    memo[(i, j)] = flag
                else:
                    flag = dfs(s, i+1, j-1) and (s[i] == s[j])
                    memo[(i, j)] = flag
                
                if flag:
                    res += 1
        
        return res

动态规划方法，注意要先遍历列，再遍历行，不要形成先遍历行再遍历列的思维定势，时间复杂度O(n^2)。

class Solution:
    def countSubstrings(self, s: str) -> int:
        '''
        state: dp[i][j]表示s[i:j]是否为回文串
        basecase: 先遍历列，再遍历行
        transfer: 若s[i]==s[j]，则dp[i][j] = dp[i+1][j-1]；
                  否则，dp[i][j] = False
        result: 每当dp[i][j] = True，res += 1， 返回res
        '''

        n = len(s)
        res = 0
        dp = [[0] * n for _ in range(n)]

        for j in range(n):
            for i in range(j+1):
                if abs(i-j) <= 1:
                    if s[i] == s[j]:
                        dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1] and s[i] == s[j]

                if dp[i][j]:
                    res += 1
        
        return res