# 1745. Palindrome Partitioning IV
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/palindrome-partitioning-iv/
## 思路
先用$O(N^2)$预处理```s``` 找到所有palindrome substring
接着遍历分界点```i```和```j```，将```s```分割为三部分，这样只需要直接调用```dp[0][i]```,```dp[i+1][j-1]```,```dp[j+1][n-1]```就可以知道这三部分是否分别都是回文串。这两层循环的时间复杂度也是$o(N^2)$.
## Code

class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i=0; i<n; i++) dp[i][i] = true;
        for(int len=2; len<=n; len++){
            for(int i=0; i+len-1<n; i++){
                int j = i+len-1;
                if(s.charAt(i)==s.charAt(j)) dp[i][j]=(j-i==1)?true:dp[i+1][j-1];
            }
        }
        
        for(int i=0; i<n; i++){
            for(int j=i+1; j+1<n; j++){
                if(dp[0][i] && dp[i+1][j] && dp[j+1][n-1]) return true;
            }
        }
        return false;
    }
}