题目要求判断一个字符串是否可以分割成三个非空回文子串。
题目描述
给定一个字符串 `s`，判断是否可以将 `s` 分割成三个非空子串 `s1`, `s2`, `s3`，使得 `s1`, `s2`, `s3` 都是回文串。如果是，返回 `true`；否则，返回 `false`。
解决思路
1. 回文判断：首先需要判断一个子串是否是回文串。可以通过动态规划预处理，记录所有子串是否是回文。
2. 分割点枚举：遍历所有可能的分割点，检查是否可以分成三个回文子串。
动态规划预处理
1. 定义 `dp[i][j]` 表示字符串 `s` 从第 `i` 个字符到第 `j` 个字符是否是回文串。
2. 状态转移方程：
- 如果 `s[i] == s[j]`，则 `dp[i][j] = dp[i+1][j-1]`。
- 如果 `i == j`，则 `dp[i][j] = true`。
- 如果 `j = i + 1`，则 `dp[i][j] = (s[i] == s[j])`。
代码实现
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool checkPartitioning(string s) {
int n = s.size();
// 预处理 dp 数组
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j]) {
if (j - i <= 1) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
}
}
// 枚举分割点
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (dp[0][i - 1] && dp[i][j - 1] && dp[j][n - 1]) {
return true;
}
}
}
return false;
}
};
复杂度分析
1. 时间复杂度：O(n^2)，其中 `n` 是字符串的长度。预处理 `dp` 数组需要 O(n^2)，枚举分割点需要 O(n^2)。
2. 空间复杂度：O(n^2)，用于存储 `dp` 数组。
边界情况
1. 字符串长度小于 3：无法分割成三个非空子串，直接返回 `false`。
2. 整个字符串是回文：可以分割成三个相同的子串。
3. 无法找到合适的分割点：返回 `false`。
总结
通过动态规划预处理回文子串信息，再枚举所有可能的分割点，可以高效地解决这个问题。时间复杂度为 _O(n^2)_，适用于中等长度的字符串。