LeetCode 132. 分割回文串 II

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的最少分割次数 。

例：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

方法：动态规划

• isPalindromic[i][j] 记录下标为 [i, j] 组成的字符串是否为回文串，True 表示为回文串，False 表示不为回文串
• 外部循环为从下到上的循环，内部循环为从左到右的循环
  • 若首尾字符不同，那么一定不为回文串
  • 若首尾字符相同，那么需要继续判断：若 i=j，即此时只有一个字符（e.g. a），那么一定为回文串；若 j-i=1，即只有两个字符且相等（e.g. aa），那么一定为回文串；若 j-i>1，即首尾字符间存在其他字符，那么此时应判断下标为 [i+1, j-1] 组成的字符串是否为回文串，即 dp[i+1][j-1]
    ※ 思路同 647. 回文子串
• dp[i] 记录下标为 [0, i] 组成的字符串使其子串均为回文串的最少分割次数。因为记录的是最少分割次数，所以初始化应为最大值正无穷，并且初始化 dp[0] 为零
• 外部循环为对字符串 s 的循环
  • 判断此时的字符串 [0, i] 是否回文，若回文则不需分割，将 dp[i] 设为零
  • 若不回文则需进行分割，循环，j 表示分割点的下标，那么此时字符串分为 [0, j] 和 [j+1, i] 两部分，若第二部分回文，那么 dp[i] 的一个选择是 dp[j]+1。因为求最少分割次数，所以取最小值

class Solution(object):
    def minCut(self, s):
        isPalindromic = [[False] * len(s) for row in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j-i <= 1 or isPalindromic[i+1][j-1]:
                        isPalindromic[i][j] = True

        dp = [float('INF')] * len(s)
        dp[0] = 0
        for i in range(1, len(s)):
            if isPalindromic[0][i]:
                dp[i] = 0
                continue
            for j in range(i):
                if isPalindromic[j+1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]

参考

代码相关：https://programmercarl.com/0132.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2II.html