LeetCode 1745.分割回文串IV（动态规划）

题目

给你一个字符串 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 的用户，不用再优化了。