【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 <= 2000s 只包含小写英文字母。
解题方法：动态规划
如果想用之前的方法直接AC：
在132.分割回文串 II中我们通过预处理可以在$O(n^2)$时间复杂度内得到字符串s的任一字串是否为回文串（方法简述如下：）
使用isok[i][j]表示字符串s从下标i到下标j的子串是否为回文串。若$i\geq 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| '''
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源