dynamic programming by Python with recursive formula


  • 0
    J
    # Time:  O(n^2)
    # Space: O(n^2)
    # idea: dynamic programming, nearly the same solution as Longest Palindromic Substring
    # dp[i, j] = 1                                   if i == j
    #          = s[i] == s[j]                        if j = i + 1
    #          = s[i] == s[j] && dp[i + 1][j - 1]    if j > i + 1     
    class Solution:
        def countSubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            cnt = 0
            memo = [[False for _ in range(len(s))] for __ in range(len(s))]
            for i in range(len(s)):
                for j in range(i):
                    if i - j <= 2:
                        memo[j][i] = (s[j] == s[i])
                    else:
                        memo[j][i] = (s[j] == s[i] and memo[j + 1][i - 1])
                    if memo[j][i]:
                        cnt += 1
                memo[i][i] = True
                cnt += 1
                
            return cnt
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.