132. Palindrome Partitioning II

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

 

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters only.

Solution

palindrome-partitioning-ii.py

class Solution:
    def minCut(self, s: str) -> int:
        if len(s) == 1: return 0

        n = len(s)
        dp = list(range(n))

        for mid in range(1, n):

            start = end = mid
            while start >= 0 and end < n and s[start] == s[end]:
                cut = 0 if start == 0 else dp[start - 1] + 1
                dp[end] = min(dp[end], cut)
                start -= 1
                end += 1

            start, end = mid - 1, mid
            while start >= 0 and end < n and s[start] == s[end]:
                cut = 0 if start == 0 else dp[start - 1] + 1
                dp[end] = min(dp[end], cut)
                start -= 1
                end += 1

        return dp[-1]