[LeetCode] 132. Palindrome Partitioning II

Problem : https://leetcode.com/problems/palindrome-partitioning-ii/

This problem includes 2 sub-problems.

Let isPalindrome[i][j] = True if s[i:j+1] is a palindrome string.

The transformation formula is

isPalindrome[i][j] = True,  when:

1)  s[i] == s[j]  and j - i <= 2     # i.e. "aa" or "aba"

2)  s[i] == s[j]  and isPalindrome[i+1][j-1] == True.   # i.e.  "a ****  a"

Let minCut[i] = min cut needed for s[0:i+1]

For any s[0:i+1], it can be split into 2 parts:  s[0:j] and s[j:i+1]

if s[j : j + 1] is a palindrome,  then minCut[i] = min( minCut[i], minCut[j-1] + 1 )

if s[0: j + 1] is already a palindrome, minCut[i] = 0

class Solution:
    def minCut(self, s: str) -> int:
        if not s:
            return 0
        
        # isPalindrome[i][j] = True if s[i:j+1] is palindrome string
        isPalindrome = [[False] * len(s) for _ in range(len(s))]
        
        for j in range(len(s)):
            for i in range(j+1):
                if s[i] == s[j] and (j - i <= 2 or isPalindrome[i+1][j-1] == True):
                    isPalindrome[i][j] = True
        
        
        # minCut[i] = min cut of s[0:i+1]
        minCut = [i for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if isPalindrome[j][i]:
                    if j == 0:
                        # s[0:i+1] is already a palindrome
                        # no need to cut
                        minCut[i] = 0
                        break
                    
                    minCut[i] = min(minCut[i], minCut[j-1] + 1)
    
        return minCut[-1]

The top-down memorization + backtracking solution:

class Solution:
    def minCut(self, s: str) -> int:
        
        @cache
        def isPalindrome(left, right):
            if left >= right:
                return True
            
            if right - left == 1:
                return True
                
            if s[left] == s[right-1] and isPalindrome(left+1, right-1):
                return True
            
            return False
        
        @cache
        def helper(left, right):
            if isPalindrome(left, right):
                # s[left:right] is already a palindrome. no need to cut.
                return 0
            
            result = right - left - 1
            
            for mid in range(left+1, right):
                if isPalindrome(left, mid):
                    # s[left:mid] is palindrome, we can try to cut it at 'mid' and calculate the least cut of rest of string
                    result = min(result, 1 + helper(mid, right))
            
            return result
        
        return helper(0, len(s))

Edited on 08/07/2021. Add the top-down memorization + backtracking solution.