leetcode 132 Palindrome Partitioning II

1. 题目大意

求最少切割多少次，才能将一个字符串变为全部为回文字串。

2. 解题思路

这道题目可以使用暴力进行求解，将当前字符串切割为回文串和剩余字符，然后再递归处理剩余字符串
结果ma,肯定是TLE的，时间复杂度$ n(n-1)… $

根据回文字符串的定义，如果一个字符串为回文字符串，那么在它的两头加上相同的字符，得到的新的字符串也是一个回文字符串。

核心逻辑如下，dp[j][i]dp[j][i]表示从j到i是否可以为回文字串，cut[i]cut[i] 表示到第i个字符需要被切割的最少次数

1
2
3
4
5
6
7
8
if dp[j] == dp[i] && (j > i - 2 || dp[j+1][i-1]) {
    dp[i][j] = true
    if j == 0 {
        min = 0 // 此时不需要进行切割 
    } else {
        min = min(m, cut[j-1]+1) //  否则切割一次
    }
}

3. code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
func minCut(s string) int {
	n := len(s)
	dp := make([][]bool, n)
	for i, _ := range dp {
		dp[i] = make([]bool, n)
	}
	cut := make([]int, n)
	for i := 0; i < n; i++ {
		m := i
		for j := 0; j <= i; j++ {
			if s[j] == s[i] && (j+1 > i-1 || dp[j+1][i-1]) {
				dp[j][i] = true
				if j == 0 {
					m = 0
				} else {
					m = min(m, cut[j-1]+1)
				}
			}
		}
		cut[i] = m
	}
	return cut[n-1]
}