一个字符串用最少刀数切出来的子串都是回文串，返回其中一种划分结果 。
此题是昨天的每日一题的变种。
对字符串范围做是否是回文串的dp。dp[i][j]=true是[i,j]范围上是回文串，dp[i][j]依赖左下方。消耗O(N2)的空间。
再弄个dp2，相当于方法一的递归。dp2[i]相当于从i的位置切下去。消耗O(N)的空间。
根据dp2，动态规划回溯，就能求出答案。跟昨天的每日一题不同的地方，就是这里。
时间复杂度是O(N2)。空间复杂度是O(N**2)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
s := "moonfdd"
ret := minCutOneWay(s)
fmt.Println(ret)
}
func minCutOneWay(s string) []string {
ans := make([]string, 0)
if len(s) < 2 {
ans = append(ans, s)
} else {
N := len(s)
checkMap := createCheckMap(s, N)
dp := make([]int, N+1)
dp[N] = 0
for i := N - 1; i >= 0; i-- {
if checkMap[i][N-1] {
dp[i] = 1
} else {
next := math.MaxInt64
for j := i; j < N; j++ {
if checkMap[i][j] {
next = getMin(next, dp[j+1])
}
}
dp[i] = 1 + next
}
}
// dp[i] (0....5) 回文！ dp[0] == dp[6] + 1
// (0....5) 6
for i, j := 0, 1; j <= N; j++ {
if checkMap[i][j-1] && dp[i] == dp[j]+1 {
ans = append(ans, s[i:j])
i = j
}
}
}
return ans
}
func createCheckMap(str string, N int) [][]bool {
ans := make([][]bool, N)
for i := 0; i < N; i++ {
ans[i] = make([]bool, N)
}
for i := 0; i < N-1; i++ {
ans[i][i] = true
ans[i][i+1] = str[i] == str[i+1]
}
ans[N-1][N-1] = true
for i := N - 3; i >= 0; i-- {
for j := i + 2; j < N; j++ {
ans[i][j] = str[i] == str[j] && ans[i+1][j-1]
}
}
return ans
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
