132. 分割回文串 II

Python示例

Python 会超时

def isPalindrome(s, start, end):
    i, j = start, end 
    while i < j:
        if s[i] != s[j]:
            return False 
        i += 1
        j -= 1
    return True 

class Solution:
    def minCut(self, s: str) -> int:
        if len(s) == 0 or len(s) == 1: return 0
        dp = [0] * (len(s) + 1) 
        dp[0] = -1 # -1 非常重要， 当 aa dp[2] = dp[0] + 1 = 0  
        dp[1] = 0
        for i in range(2, len(s) + 1):
            dp[i] = i - 1 # dp[i]代表前 i 个字符串的最少切分
            for j in range(i):
                if isPalindrome(s, j, i - 1): # j - i-1 是
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]

Go 不会超时

func isPalindrome(s string, start int, end int) bool {
    for i, j := start, end; i < j; i, j = i + 1, j - 1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true 
}

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

func minCut(s string) int {
    if len(s) == 0 || len(s) == 1 { return 0}
    dp := make([]int, len(s) + 1)
    dp[0] = -1 
    dp[1] = 0
    for i := 2; i < len(s) + 1; i++ {
        dp[i] = i - 1
        for j := 0; j < i; j++ {
            if isPalindrome(s, j, i - 1) {
                dp[i] = min(dp[i], dp[j] + 1) 
            }
        }
    }
    return dp[len(s)]
}