132. Palindrome Partitioning II #

题目 #

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

Return theminimum 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.

代码 #

package leetcode

func minCut(s string) int {
	if s == "" {
		return 0
	}
	result := len(s)
	current := make([]string, 0, len(s))
	dfs132(s, 0, current, &result)
	return result
}

func dfs132(s string, idx int, cur []string, result *int) {
	start, end := idx, len(s)
	if start == end {
		*result = min(*result, len(cur)-1)
		return
	}
	for i := start; i < end; i++ {
		if isPal(s, start, i) {
			dfs132(s, i+1, append(cur, s[start:i+1]), result)
		}
	}
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func isPal(str string, s, e int) bool {
	for s < e {
		if str[s] != str[e] {
			return false
		}
		s++
		e--
	}
	return true
}