LeetCode: 132. Palindrome Partitioning II

 

1. Bottom-up Solution + predefining palindromic matrix

class Solution:
    def minCut(self, s: str) -> int:
        dp = self.build_palindrome(s)
        n = len(s)
        self.cut = [2002] * n
        for end in range(n):
            if dp[0][end]:
                self.cut[end] = 0
                continue
            for start in range(1, end+1):
                if dp[start][end]:
                    self.cut[end] = min(self.cut[end], self.cut[start-1] + 1)
        return self.cut[-1]
        
    def build_palindrome(self, word):
        n = len(word)
        dp = [[False] * n for _ in range(n)]
        for end in range(n):
            for start in range(end+1):
                if word[end] == word[start] and (end - start <= 2 or dp[start+1][end-1]):
                    dp[start][end] = True
        return dp

 

2. Top-down Solution + predefining palindromic matrix

class Solution:
    def minCut(self, s: str) -> int:
        self.dp = self.build_palindrome(s)
        self.cut = [2001] * len(s)
        self.helper(s, len(s)-1)
        return self.cut[-1]
        
    def helper(self, s, end):
        if self.cut[end] != 2001:
            return self.cut[end]
        if end == 0:
            self.cut[end] = 0
            return 0
        if self.dp[0][end]:
            self.cut[end] = 0           
            return 0
        for start in range(end, 0, -1):
            if self.dp[start][end]:
                self.cut[end] = min(self.cut[end], self.helper(s, start-1)+1)
        return self.cut[end]
        
    def build_palindrome(self, word):
        n = len(word)
        dp = [[False] * n for _ in range(n)]
        for end in range(n):
            for start in range(end+1):
                if word[end] == word[start] and (end - start <= 2 or dp[start+1][end-1]):
                    dp[start][end] = True
        return dp