题目
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = “abcbdd”
输出：true
解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。
示例 2：
输入：s = “bcbddxy”
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000
s 只包含小写英文字母。
思路
如果枚举两个边界，相当于O(N^2）复杂度。此时再使用双指针判断每一部分是否是回文，复杂度为O（N）,那么整体复杂度就是O(N的三次方)。
为此我们需要将判断是否是回文的部分降为O(1)，此时我们使用动态规划，定义布尔二维数组f[i][j]
f[i][j]=1表示从i到j的子串是回文字符串，为0则表示不是。那么可以写出动态规划方程
f[i][j]=
- 当i=j时，一定为true
- 当i+1=j时，值为s[i]==s[j]
- 当j-i>1时，值为s[i]==s[j]&&f[i+1][j-1]
由最后一个情况可以看出，计算f[i][j]时一定要先计算出f[i+1][j-1]。那么i必须要从大到小遍历，j必须要从小到大遍历，且从i开始遍历。
代码
class Solution {
public boolean checkPartitioning(String str) {
char[] s = str.toCharArray();
int size = s.length;
boolean[][] f = new boolean[size][size];
for(int i = size-1;i>=0;i--){
for(int j = i;j<size;j++){
if(i==j) f[i][j]=true;
else if(i+1==j) f[i][j]=(s[i]==s[j]);
else {
f[i][j]=(s[i]==s[j])&&(f[i+1][j-1]);
}
}
}
for(int i=1;i<=size-2;i++){
for(int j=i;j<=size-1;j++){
if(f[0][i-1]&&f[i][j-1]&&f[j][size-1]) return true;
}
}
return false;
}
}
效率分析
74ms，击败74.77%使用 Java 的用户，不用再优化了。
