I'm trying to solve the number of palindromic substrings problem using DP.

The problem requires us to find the number of palindromic substrings in a string.

My current code is as follows:

def palindromic_substrings(s):
  result = 0

  dp = [[False]*len(s) for i in range(len(s))]

  for i in range(len(s)):
    for j in range(i, len(s)):
      dp[i][j] = j - i <= 1 or (s[i] == s[j] and dp[i 1][j-1])
      if dp[i][j]:
        result  = 1
  

  return result


print(palindromic_substrings("aaa")) # returns 5- should be 6

My logic is a follows:

Let dp[i][j] represents whether the substring defined by s[i:j] is a palindromic substring. There are two cases to consider to determine dp[i][j].

The first is noticing that any substring of length less than 2 is always a palindrome i.e. j-i <= 1.

The second is that any substring that has length greater than 2 is a palindrome iff the first and last characters are the same and the inner substring, excluding the first and last characters is a palindrome i.e. s[i] == s[j] and dp[i 1][j-1].

If dp[i][j] is True i.e. it is palindromic, we increment the result.

My code is returning the wrong result and I'm unsure where the gap in my logic is.

Any help would be appreciated.

CodePudding user response：

This is inspired by @Stef great comments, so the working code will be like this: (credit to him, question for me... ;-)

def countSubstrings(self, s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
        
    ans = 0
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            dp[i][j] = s[i] == s[j] and ((j-i 1) < 3 or dp[i 1][j-1])
            ans  = dp[i][j]
    return ans

And this is non-DP version to compare:

 def countSubstrings(self, s: str) -> int:
     count = 0
     n = len(s)

     for i in range(2 * n - 1):

         left  =  i // 2
         right = (i 1) //  2
            
         while left >= 0 and right <n and s[left] == s[right]:
             count  = 1
             left -= 1
             right  = 1

     return count