Python DP solution but TLE


  • -1
    P

    The algorithm uses list ptable to record whether a sub-string is a palindrome or not. ptable[i][j] == True means a sub-string starts from s[i] (inconclusive) to s[j] (inclusive) is a palindrome. Use list dp[i] to record the minimum number of palindromes within a sub-string start from s[i], dp[i] == 3 means a substring starts from s[i] (inconclusive) to the end (inclusive) has 3 palindromes and 3 is the minimum number. When ptable[i][j] == True case, we update list dp with dp[i]=min(dp[i],1+dp[j+1]). Finally the minimum cut is dp[0] - 1.

    class Solution:
        # @param s, a string
        # @return an integer
        def minCut(self, s):
            n=len(s)
            ptable=[[False for i in range(n)]for j in range(n)]
            dp=[n-i for i in range(n+1)]
            for i in range(n-1,-1,-1):
                for j in range(i,n):
                    if s[i]==s[j] and (j-i<2 or s[i+1]==s[j-1]):
                        ptable[i][j]=True
                        dp[i]=min(dp[i],1+dp[j+1])
            return dp[0]-1

Log in to reply
 

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