↓Skip to main content
  1. Posts/

LeetCode-132 分割回文串 II

·1 min·
Table of Contents

LeetCode-132 分割回文串 II #

Solution 1 #

预处理区间是否是回文串, 回溯.

代码如下:

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        dp = [[False for _ in range(n)] for _ in range(n)]
        for l in range(1, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                dp[i][j] = (dp[i + 1][j - 1] if i + 1 <= j - 1 else True) and s[i] == s[j]
        @cache
        def f(i):
            if dp[i][n - 1]:
                return 0
            res = inf
            for j in range(i, n - 1):
                if dp[i][j]:
                    res = min(res, 1 + f(j + 1))
            return res
        return f(0)