[python 100ms] Extra dealing with super long cases reduces time cost from 576ms to 100ms


  • 3
    S

    The main method that uses double dp is nothing novel.
    However, if I add a few more lines at the beginning to avoid the long cases in which mincut = 0 or mincut = 1, the time cost optimized so dramatically that I got really surprised...

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

Log in to reply
 

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