> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/132.-palindrome-partitioning-ii.md).

# 132. Palindrome Partitioning II

## LeetCode [132. Palindrome Partitioning II](https://leetcode-cn.com/problems/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
```

**Constraints:**

* `1 <= s.length <= 2000`
* `s` consists of lower-case English letters only.

### Tags

Dynamic Programming

### Solution

We denote $$f\[i]$$ as the least number of cuts `s[0..i]` needs. We can formulate its transition function as below:

$$f\[i] = \min {f\[j]}+1, 0\leq j\leq i, s\[j+1..i] ,is,a,palindrome$$

There is an edge case leads $$f\[i]=0$$ when $$s\[0..i] ,is,a,palindrome$$ .

We also use a 2D array to determine every substring that whether it is a palindrome, with the dynamic programming solver below:

![](/files/mx9f6qjdLgs1dn44yUB7)

### Complexity

* Time complexity: $$O(n)$$
* Space complexity: $$O(n)$$

### Code

```go
func minCut(s string) int {
	g := make([][]bool, len(s))
	for i := range g {
		g[i] = make([]bool, len(s))
		for j := range g[i] {
			g[i][j] = true
		}
	}
	for i := len(s) - 1; i >= 0; i-- {
		for j := i + 1; j < len(s); j++ {
			g[i][j] = s[i] == s[j] && g[i+1][j-1] // s[i+1..j-1] is a palindrome
		}
	}
	f := make([]int, len(s)) // f[i] = min{f[j]}+1 && s[j+1..i] is a palindrome
	for i := range f {
		if g[0][i] { // If s[0..i] is a palindrome, it needs 0 cut.
			continue
		}
		f[i] = 1 << 31
		for j := 0; j < i; j++ {
			if g[j+1][i] && f[j]+1 < f[i] { // s[j+1..i] is a palindrome
				f[i] = f[j] + 1
			}
		}
	}
	return f[len(s)-1]
}
```

## Reference

1. [分割回文串 II](https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/fen-ge-hui-wen-chuan-ii-by-leetcode-solu-norx/)