2021-06-08：一个字符串至少要切几刀能让切出来的子串都是回文串？

2021-06-08：一个字符串至少要切几刀能让切出来的子串都是回文串？

福大大 答案2021-06-08：

方法一、自然智慧，从左往右，尝试切。回文判断是O(N2)。
时间复杂度是O(N3)，空间复杂度是O(N)。

方法二、对字符串范围做是否是回文串的dp。dp[i][j]=true是[i,j]范围上是回文串，dp[i][j]依赖左下方。消耗O(N2)的空间。
再弄个dp2，相当于方法一的递归。dp2[i]相当于从i的位置切下去。消耗O(N)的空间。
时间复杂度是O(N2)。空间复杂度是O(N**2)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().Unix())
    const TOTAL = 100
    count := 0
    for i := 0; i < TOTAL; i++ {
        s := genRandString()
        ret1 := minCut1(s)
        ret2 := minCut2(s)
        if ret1 == ret2 {
            count++
        }
        fmt.Println(s, ret1, ret2)
    }
    fmt.Println("总数：", TOTAL)
    fmt.Println("正确数：", TOTAL)
}

func genRandString() string {
    ans := make([]byte, rand.Intn(5)+50)
    for i := 0; i < len(ans); i++ {
        ans[i] = byte('A' + rand.Intn(26))
    }
    return string(ans)
}

func isPalindromeString(s string) bool {
    if len(s) <= 1 {
        return true
    }
    N := len(s)
    for i := 0; i < N/2; i++ {
        if s[i] != s[N-i-1] {
            return false
        }
    }
    return true
}

//自然智慧，递归。
func minCut1(s string) int {
    if len(s) <= 1 {
        return 0
    }
    return process(s, 0, 0) - 1
}

func process(s string, start int, cut int) int {
    if start == len(s) {
        return cut
    }
    N := len(s)
    ans := math.MaxInt64
    for i := start + 1; i <= N; i++ {
        if isPalindromeString(s[start:i]) {
            ans = getMin(process(s, i, cut+1), ans)
        }
    }
    return ans
}

func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

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 minCut2(s string) int {
    if len(s) < 2 {
        return 0
    }
    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
        }
    }
    return dp[0] - 1
}

执行结果如下：