# O(n^2) DP Solution, beat 100% Python for now

• Use a table is_palin[x][y] to memorize if s[x: y + 1] is a palindromic string, 1 for yes and 0 for no. Then just simply construct this DP table starting from the one character case to len(s) characters case.

``````class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
#is_palin[x][y] ==> s[x: y + 1] is a palindromic string?
#1 for yes, 0 for no
is_palin = [[0] * (len(s)) for _ in xrange(len(s))]
#initialize situation of one & two characters
for index in xrange(len(is_palin)):
is_palin[index][index] = 1
for start in xrange(len(is_palin) - 1):
is_palin[start][start + 1] = 1 if s[start] == s[start + 1] else 0
#construct DP table
for length in xrange(2, len(s)):
for start in xrange(len(s) - length):
is_palin[start][start + length] = 1 \
if is_palin[start + 1][start + length - 1]\
and s[start] == s[start + length] else 0
#sum over the whole DP table
return sum([is_palin[x][y] for x in xrange(len(s)) for y in xrange(len(s))])
``````

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