Skip to content

132. Palindrome Partitioning II

String Dynamic Programming

Problem - Palindrome Partitioning II

Hard

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.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        graph = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                graph[i][j] = s[i] == s[j] and graph[i + 1][j - 1]

        dp = list(range(n))
        for i in range(1, n):
            for j in range(i + 1):
                if graph[j][i]:
                    dp[i] = min(dp[i], dp[j - 1] + 1 if j else 0)

        return dp[-1]

Submission Stats:

  • Runtime: 779 ms (42.25%)
  • Memory: 49.1 MB (37.38%)