132. 分割回文串 II

Difficulty
Hard
Tags
动态规划
字符串
URL
https://leetcode-cn.com/problems/palindrome-partitioning-ii/
Star
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将s分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：
  • 1 <= s.length <= 2000
  • s 仅由小写英文字母组成

动态规划

思路
dp[i] 以s[i] 结尾的字符串，最少需要分割的次数。
初始时，将dp[i]最大化为i
如果s[j:i+1] 为回文串，那么dp[i] = min(dp[i], dp[j-1]+1)
所以就在于寻找jj应该满足s[j:i+1]为回文串
在寻找j的时候尽可能的优化，尽可能的提前截止。
题解
class Solution:
    def minCut(self, s: str) -> int:
        if len(s) <= 1:
            return 0

        # 判断 s[i:j+1] 是否为回文串
        def check(s, j, i):
            while j < i and s[i] == s[j]:
                j += 1
                i -= 1
            return j >= i

        # 初始化为 最大分割次数
        # dp[i] 为 以 s[i ]结尾的字符串 最少分割次数
        dp = [i for i in range(len(s))]

        for i in range(1, len(dp)):
            # 此时的最差情况
            dp[i] = dp[i-1] + 1
            # 向前寻找 j
            for j in range(i, -1, -1):
                if check(s, j, i):
                    if j > 0:
                        dp[i] = min(dp[i], dp[j-1]+1)
                    else:
                        dp[i] = 0
                # 做一个简单的优化
                # 如果dp[i] == 1, 已经差不多是最优了，
                # 此时只需要再看一下s[0:i]是不是回文串
                if dp[i] == 1:
                    if check(s,0,i):
                        dp[i] = 0
                    break

        return dp[-1]
注意：本题的check函数每次都用来判断一次，其实可以维护一个memo[i][j] 数组，用来记录s[i:j+1]是否为回文串。
class Solution:
    def minCut(self, s: str) -> int:
        if len(s) <= 1:
            return 0

        # memo[i][j] 为s[i][j] 是否为回文串
        memo = [[True]* len(s) for _ in s]

        for i in range(len(s), -1, -1):
            for j in range(i+1, len(s), 1):
                if s[i] == s[j]:
                    memo[i][j] = memo[i+1][j-1]
                else:
                    memo[i][j] = False

        dp = [i for _ in range(len(s))]

        for i in range(1, len(s)):
            dp[i] = dp[i-1] + 1
						# 向前寻找j
            for j in range(i, -1, -1):
                if memo[j][i]:
                    if j > 0:
                        dp[i] = min(dp[i], dp[j-1]+1)
                    else:
                        dp[i] = 0
                
								# 提前截止 寻找j的过程
                if dp[i] == 1:
                    if memo[0][i]:
                        dp[i] = 0
                    break
        
        return dp[-1]