Clean Python DP solution, O(n) space


  • 0
    C
    class Solution(object):
        def minCut(self, s):
            n = len(s)
    
            def update_cuts(left, right):
                while 0 <= left <= right < n and s[left] == s[right]:
                    # Either include a new palindrome with one additional cut or not.
                    cuts[1 + right] = min(cuts[1 + right], 1 + cuts[left])
                    left -= 1
                    right += 1
            
            cuts = [i - 1 for i in range(n + 1)]
    
            for i in range(n):
                left, right = i, i
                update_cuts(left, right)
                
                left, right = i, i + 1
                update_cuts(left, right)
    
            return cuts[-1]
    

Log in to reply
 

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