132. 分割回文串 II

https://leetcode-cn.com/problems/palindrome-partitioning-ii/

解法一：回溯（超时）：

思路类似于131分割回文串

class Solution:
    def minCut(self, s: str) -> int:
        self.minCount = sys.maxsize  #记录回文串最少数目
        self.dfs(s, 0, 0)
        return self.minCount - 1  #最少数目-1即为最少分割次数
        
    #回溯，从idx后开始处理，count计数当前找到的回文串数
    def dfs(self, s, idx, count):
        if idx == len(s):
            self.minCount = min(self.minCount, count)
        #截取长度从1开始，分别试探
        for i in range(idx+1, len(s)+1):            
            if self.isPalindrome(s[idx:i]):
                self.dfs(s, i, count+1)
                
    def isPalindrome(self, s):
        return s == s[::-1]

解法二：dp

类似于 5.最长回文子串 的dp解法。用一个isPal矩阵表示是否回文串，再加一个一维数组dp记录最小分割次数，dp[i]表示s[i : n-1]字符串的最小分割次数。

i从n-1到0。j在[i : n-1]变动，若检测到s[i : j]是回文串，则：

1.若j==n-1，则s[i : n-1]段的分割次数为0，即dp[i]=0

2.若j !=-1，则s[i : n-1]可以分解为子问题：s[i : j]和s[j+1 : n-1]。s[i : j]段要切一次，s[j+1 : n-1]要切dp[j+1]次，此外还要求最小切割次数，即dp[i] = min(dp[i], dp[j+1] + 1)

class Solution:
    def minCut(self, s: str) -> int:
        maxLen = 0
        n = len(s)
        dp = [n] * n  #最小分割次数
        isPal = [[0 for i in range(n)] for i in range(n)]  #是否回文串
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i < 3 or isPal[i+1][j-1]):
                    dp[i] = 0 if j==n-1 else min(dp[i], dp[j+1]+1)
                    isPal[i][j] = 1
        return dp[0]

此外j从大到小也可以（待解释

class Solution:
    def minCut(self, s: str) -> int:
        maxLen = 0
        n = len(s)
        dp = [n] * n  #最小分割次数
        isPal = [[0 for i in range(n)] for i in range(n)]  #是否回文串
        for i in range(n-1, -1, -1):
            for j in range(n-1, i-1, -1):  #j从大到小
                if s[i] == s[j] and (j - i < 3 or isPal[i+1][j-1]):
                    dp[i] = 0 if j==n-1 else min(dp[i], dp[j+1]+1)
                    isPal[i][j] = 1
        return dp[0]