647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/

Python

Bottom-Up DP

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)


        dp = [[0]*n for _ in range(n)]
        result = 0

        # Initial of DP matrix, with diagonal has value 1
        # Since every single character is a palindromic substring
        #  a a a
        #a 1 0 0
        #a 0 1 0
        #a 0 0 1
        for i in range(n):
            dp[i][i] = 1
            result += 1

        # If the neighbor char is the same to self,
        # the pair of neighbor is a palindromic substring
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = 1
                result += 1

        for length in range(3, n+1):
            for i in range(n-length+1):
                j = i+length-1
                if dp[i+1][j-1] and s[i] == s[j]:
                    dp[i][j] = 1
                    result += 1

        return result