题目描述
给定一个字符串 s
,如果可以将它分割成三个 非空 回文子字符串,那么返回 true
,否则返回 false
。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串。
样例
输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
限制
3 <= s.length <= 2000
s
只包含小写英文字母。
算法
(区间动态规划,暴力枚举) $O(n^2)$
- 使用动态规划预处理区间 $[l, r]$ 是否为回文子串。定义状态 $judge(l, r)$ 为区间 $[l, r]$ 是否为回文子串。
- 初始时所有位置的值待定。
- 区间长度从 1 开始枚举到 $n$。对于区间 $[i, j]$,如果 $s(i) == s(j)$ 下,$j - i <= 1$ 或 $judge(i + 1, j - 1)$ 为 $true$ 时,则 $judge(i, j)$ 为 $true$。
- 预处理完成后,枚举两个断点的位置,判断是否存在三个非空子串满足条件。
时间复杂度
- 动态规划的状态数为 $O(n^2)$,转移时间为 $O(1)$。
- 枚举答案的时间复杂度为 $O(n^2)$。
- 故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n^2)$ 的空间存储动态规划的状态(预处理的数组)。
C++ 代码
class Solution {
public:
bool checkPartitioning(string s) {
const int n = s.size();
vector<vector<bool>> judge(n, vector<bool>(n, false));
for (int len = 1; len <= n; len++)
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
judge[i][j] = (s[i] == s[j] && (j - i <= 1 || judge[i + 1][j - 1]));
}
for (int i = 1; i < n; i++)
for (int j = i + 1; j < n; j++)
if (judge[0][i - 1] && judge[i][j - 1] && judge[j][n - 1])
return true;
return false;
}
};