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

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

力扣题目链接： leetcode /problems/palindrome-partitioning-iv/

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

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

 

示例 1：

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

示例 2：

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

 

提示：

3 <= s.length <= 2000s​​​​​​ 只包含小写英文字母。 解题方法：动态规划

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

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

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

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

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

时间复杂度 O ( n 2 ) O(n^2) O(n2)，其中 n = l e n ( s ) n=len(s) n=len(s)空间复杂度 O ( n 2 ) O(n^2) O(n2) 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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源