223 - 132 分割回文串

题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab" 输出: 1 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

解答

最坏情况，按照每个字母分割

https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/zi-ding-xiang-xia-he-zi-di-xiang-shang-by-powcai-2/

class Solution:
    def minCut(self, s: str) -> int:
        min_s = list(range(len(s)))
        n = len(s)
        dp = [[False]*n for _ in range(n)]
        for i in range(n):
            for j in range(i+1):
                if s[i] == s[j] and (i-j < 2 or dp[j+1][i-1]):
                    dp[j][i] = True
                    if j == 0:
                        min_s[i] = 0
                    else:
                        min_s[i] = min(min_s[i], min_s[j-1]+1)
        return min_s[-1]

Runtime: 408 ms, faster than 66.52% of Python3 online submissions for Palindrome Partitioning II.

Memory Usage: 29.5 MB, less than 90.00% of Python3 online submissions for Palindrome Partitioning II.

https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-by-liweiwei1419-2/

李威威大佬的题解

• dp表示最小分割次数

• 状态转移：

  遍历j到i，如果s[j+1: i]是回文，那么就在dp[j]的基础上多分割一次即可

class Solution:
    def minCut(self, s: str) -> int:
        size = len(s)
        if size < 2:
            return 0
        dp = [i for i in range(size)]
        checked = [[False for _ in range(size)] for _ in range(size)]
        for right in range(size):
            for left in range(right+1):
                if s[left] == s[right] and (right-left <= 2 or
                                            checked[left+1][right-1]):
                    checked[left][right] = True
        for i in range(1, size):
            if checked[0][i]:
                dp[i] = 0
                continue
            dp[i] = min([dp[j]+1 for j in range(i) if checked[j+1][i]])

        return dp[size-1]

Runtime: 468 ms, faster than 59.74% of Python3 online submissions for Palindrome Partitioning II.

Memory Usage: 31.2 MB, less than 80.00% of Python3 online submissions for Palindrome Partitioning II.