LeetCode-1745 分割回文串 IV

Table of Contents

LeetCode-1745 分割回文串 IV #

Solution 1 #

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

代码如下:

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        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, k) -> bool:
            if k == 0:
                return i == n
            for j in range(i, n):
                if dp[i][j] and f(j + 1, k - 1):
                    return True
            return False
        return f(0, 3)