python实现leetcode之132. 分割回文串 II

解题思路

先构建一张表grid

grid[x][y]是s[x, y)是不是回文的布尔值
其中x <= y, x == y表示空串

然后使用动态规划，划分次数非递增序收紧
针对每个位置：

它往反方向找到一个回文，切分他的最小次数就是该位置减去找到的回文后切分的最小次数，然后+1
扫遍所有位置，如果从头到该位置就一个回文，那么不用切分

132. 分割回文串 II

代码

class Solution:
    def minCut(self, s: str) -> int:
        """
        dp[index]是s[:index]的最少分割数
        """
        N = len(s)
        grid = build_palindrome_grid(s)
        dp = [N for _ in range(N+1)]
        dp[0] = dp[1] = 0
        idx = 2
        while idx < len(dp):
            back_idx = idx - 1  # 逆方向的下标索引
            while back_idx >= 0:
                if grid[back_idx][idx]:
                    if back_idx == 0:
                        dp[idx] = 0
                    dp[idx] = min(dp[idx], dp[back_idx] + 1)
                back_idx -= 1
            idx += 1
        return dp[N]


def build_palindrome_grid(s):
    """
    grid[x][y]是s[x, y)是不是回文的布尔值
    其中x <= y, x == y表示空串
    """
    grid = [[False for _ in range(len(s)+1)][:] for c in range(len(s)+1)]
    for y in range(len(grid)):
        for x in range(y):
            if x == y - 1:  # s[y-1:y] == s[y-1]肯定是回文
                grid[x][y] = True
            else:
                grid[x][y] = grid[x+1][y-1] and s[x] == s[y-1]
        grid[y][y] = True
    return grid