题目描述
给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。
示例 1:
输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
示例 2:
输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
提示:
3 <= s.length <= 2000
s 只包含小写英文字母。
算法1
先看同一系列的 回文串分割
我们可以使用dp[i][j] 表示字符串i到j的子字符串是否是回文。
那么状态转移方程 如图
然后包里遍历分割点 point1 point2 ,将字符串分成三段,直接检测DP判断三段字符串是否是回文
C++ 代码
class Solution {
public:
vector<vector<int>> dp;
void initDp(const string& s)
{
//计算dp[i][j] 字符串s的i到j的子字符串是否是回文
dp = vector<vector<int>>(s.size() + 10, vector<int>(s.size() + 10));
for (int i = 0; i < s.size(); i++) { dp[i][i] = 1; }
for (int i = 0; i < s.size() - 1; i++) {
int l = i - 1; int r = i + 1;
while (l >= 0 && r < s.size() && s[l] == s[r]) {
dp[l][r] = 1; l--; r++;
}
l = i - 1; r = i + 2;
if (s[i] == s[i + 1]) dp[i][i + 1] = 1;
while (l >= 0 && r < s.size() && s[l] == s[r] && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
dp[l][r] = 1; l--; r++;
}
}
}
bool checkPartitioning(string s) {
initDp(s);
for(int i = 0; i < s.size();i++){
for(int j = i+1;j<s.size();j++){
if(dp[0][i] && dp[i+1][j] && dp[j+1][s.size()-1]) return true;
}
}
return false;
}
};