Simple implementation in python (brute force and dynamic programming)


  • 0
    S

    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

Log in to reply
 

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