算法题记录 21

1745.分割回文串4（1925）

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

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

涉及知识点

字符串，dfs

解决思路

还是分割回文串的思路，当计数为3时返回true即可，否则最后返回false。

class Solution:
    def minCut(self, s: str) -> int:
        # 返回 s[l:r+1] 是否为回文串
        @cache  # 缓存装饰器，避免重复计算 is_palindrome（一行代码实现记忆化）
        def is_palindrome(l: int, r: int) -> bool:
            if l >= r:
                return True
            return s[l] == s[r] and is_palindrome(l + 1, r - 1)

        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(r: int) -> bool:
            flag=0
            if is_palindrome(0, r):  # 已是回文串，无需分割
                if count==2:
                    return True
            count = 0
            for l in range(1, r + 1):  # 枚举分割位置
                if is_palindrome(l, r):
                    count+=1
                    if count>2:
                        return False
                    if dfs(l - 1)==True:
                        flag=1
                    count-=1
            return True if flag==1 else False

        return dfs(len(s) - 1)