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


  • 0

    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))])
    

Log in to reply
 

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