LeetCode-1745 分割回文串Ⅳ

题目描述

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

• 3 <= s.length <= 2000
• s 只包含小写英文字母。

题解

记忆化搜索+动态规划，结合前几天每日一题的框架

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        @cache
        def is_palindrome(i: int, j: int) -> bool:
            if i >= j:
                return True
            return s[i] == s[j] and is_palindrome(i + 1, j - 1)
        
        @cache
        def dfs(l: int, r: int, k: int) -> bool:
            if k <= 0:
                return is_palindrome(l, r)

            ans = False
            for i in range(r, l, -1):
                ans = dfs(l, i - 1, k - 1) and is_palindrome(i, r)
                if ans:
                    break
            return ans

        # 切两刀
        return dfs(0, len(s) - 1, 2)