Simple implementation in python (brute force and dynamic programming)

• Brute force - O(n^3)

``````class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
if s:
n   = len(s)
res += n
for l in range(2,n+1): # length ranges from 2 to n including n
for i in range(n-l+1): # start index ranges from 0 to n - l including n - l
if s[i:i+l] == s[i:i+l][::-1]:
res += 1
return res
``````

Dynamic Programming O(n^2)

``````class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
cnt = 0  # count of pallindromes encountered
if s:
n   = len(s)
# a dynamic programming table, dp[i][j] = True if s[i:j+1] is pallindrome
dp = [ [ True for j in range(n) ] for i in range(n) ]

# each character is pallindrome, so dp[i][i] = True
# also counting pallindromes of length 1
for i in range(n):
dp[i][i]  = True
cnt      += 1

for length in range(2,n+1): # length ranges from 2 to n
for start in range(n):  # start index ranges from 0 to n-1
i =  start
j  = start + length - 1    # end index for a string of length "length" starting at index start
if 0 <= i < j < n:         # if indices are within string under consideration
dp[i][j] =  False
if s[i] == s[j] and dp[i+1][j-1] == True: # if s[i] == s[j] and s[i+1:j] is pallindrome
dp[i][j] = True
cnt += 1

return cnt``````

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