132. Palindrome Partitioning II

LeetCode 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

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:

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

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