LeetCode 1745.分割回文串 IV：动态规划（用III或II能直接秒）

【LetMeFly】1745.分割回文串 IV：动态规划（用III或II能直接秒）

力扣题目链接：https://leetcode.cn/problems/palindrome-partitioning-iv/

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

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

示例 1：

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

示例 2：

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

提示：

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

解题方法：动态规划

如果想用之前的方法直接AC：

• 1278.分割回文串 III：令k = 3，复杂度$O(n^{2}k)$
• 132.分割回文串 II：也就是今天的方法。

在132.分割回文串 II中我们通过预处理可以在$O(n^2)$时间复杂度内得到字符串s的任一字串是否为回文串（方法简述如下：）

使用isok[i][j]表示字符串s从下标i到下标j的子串是否为回文串。若$i\ge j$则视为回文串，否则有状态转移方程$isok[i][j]=s[i]==s[j]\text{ AND }isok[i+1][j-1]$。

都知道任意一个字串是否是回文串了，我直接枚举两个分割位置，每次使用$O(1)$时间看看被分成的三段是否都为回文字符串不就可以了么？

• 时间复杂度$O(n^2)$，其中$n=len(s)$
• 空间复杂度$O(n^2)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-04 10:18:19
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-04 10:28:38
 */
class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> isok(n, vector<bool>(n, true));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                isok[i][j] = s[i] == s[j] && isok[i + 1][j - 1];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                if (isok[0][i] && isok[i + 1][j] && isok[j + 1][n - 1]) {
                    return true;
                }
            }
        }
        return false;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-04 10:30:23
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-04 10:33:30
'''
class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        isok = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                isok[i][j] = s[i] == s[j] and isok[i + 1][j - 1]
        for i in range(n):
            for j in range(i + 1, n - 1):
                if isok[0][i] and isok[i + 1][j] and isok[j + 1][n - 1]:
                    return True
        return False

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-03-04 10:42:05
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-04 10:46:32
 */
package main

func checkPartitioning(s string) bool {
    n := len(s)
    isok := make([][]bool, n)
    for i, _ := range isok {
        isok[i] = make([]bool, n)
        for j, _ := range isok[i] {
            isok[i][j] = true
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            isok[i][j] = s[i] == s[j] && isok[i + 1][j - 1]
        }
    }
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n - 1; j++ {
            if isok[0][i] && isok[i + 1][j] && isok[j + 1][n - 1] {
                return true
            }
        }
    }
    return false
}

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-03-04 10:47:02
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-04 10:49:14
 */
class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isok = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                isok[i][j] = true;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                isok[i][j] = s.charAt(i) == s.charAt(j) && isok[i + 1][j - 1];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                if (isok[0][i] && isok[i + 1][j] && isok[j + 1][n - 1]) {
                    return true;
                }
            }
        }
        return false;
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源