题目描述
给你一个字符串 s
,如果可以将它分割成三个 非空 回文子字符串,那么返回 true
,否则返回 false
。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。
样例
输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
提示:
3 <= s.length <= 2000
s
只包含小写英文字母。
算法分析
区间dp
预处理$O(n^2)$
状态表示:f[i][j]
表示区间[i, j]
是否是一个回文串
状态计算:
- 当
i == j
时,f[i][j] = true
(回文串是奇数) - 当
i == j + 1
时,f[i][j] = true
(回文串是偶数) - 当
j - i + 1 > 2
时(区间长度大于2
),s[i] == s[j]
并且f[i + 1][j - 1] = true
,则f[i][j] = true
- 其余都是
f[i][j] = false
操作:
- 将该子串分割成
3
个段,因此枚举两次分界线即可,分割成[0, i - 1]
,[i, j]
,[j, n - 1]
,其中(1 <= i <= j <= n - 2)
,再判断是否存在一组满足3
段都是回文串的情况
时间复杂度 $O(n^2)$
C++ 代码
class Solution {
public:
bool checkPartitioning(string s) {
int n = s.size();
vector<vector<bool>> f(n, vector<bool>(n));
for(int len = 1; len <= n;len ++)
for(int i = 0; i + len - 1 < n;i ++)
{
int j = i + len - 1;
if(i == j) f[i][j] = true;
else if(i + 1 == j && s[i] == s[j]) f[i][j] = true;
else if(s[i] == s[j] && f[i + 1][j - 1]) f[i][j] = true;
else f[i][j] = false;
}
for(int i = 1;i <= n - 2;i ++)
for(int j = i;j <= n - 2;j ++)
if(f[0][i - 1] && f[i][j] && f[j + 1][n - 1]) return true;
return false;
}
};