Python solution with detailed explanation


  • 0
    G

    Solution

    Palindrome Partitioning II https://leetcode.com/problems/palindrome-partitioning-ii/

    Memoization

    • We parameterize the problem with index k which answers the question: How many min-cuts are required to cut the string s[k:]?
    • min_cut(k) = min(min_cut(j))+1 such that s[k:j] is a palindrome
    • min_cut(k) = 0 if s[k:] is a palindrome
    class Solution(object):
        def is_palindrome(self, s):
            N = len(s)
            cache = [[False]*N for _ in range(N)]
            for i in range(N):
                cache[i][i] = True
                if i+1 < N:
                    cache[i][i+1] = (s[i] == s[i+1])
            # Incrementally build with increasing lengths from 3 to final        
            for length in range(3,len(s)+1):
                j = length-1
                for i in range(N):
                    if i+j < N:
                        cache[i][i+j] = cache[i+1][i+j-1] and (s[i] == s[i+j]) 
            return cache
        
        def minCut(self, s):
            """
            :type s: str
            :rtype: int
            """
            cache_dp = {}
            return self.helper(0, s, self.is_palindrome(s), cache_dp)
            
        def helper(self, k, s, cache, cache_dp):
            if k in cache_dp:
                return cache_dp[k]
            else:
                cache_dp[k] = float('inf')
                for i in range(k, len(s)):
                    if cache[k][i]:
                        cache_dp[k] = 0 if i == len(s)-1 else min(cache_dp[k], self.helper(i+1, s, cache, cache_dp)+1)
                return cache_dp[k]
    

Log in to reply
 

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