<p>Given a string <code>s</code>, return <code>true</code> <em>if it is possible to split the string</em> <code>s</code> <em>into three <strong>non-empty</strong> palindromic substrings. Otherwise, return </em><code>false</code>.​​​​​</p>

<p>A string is said to be palindrome if it the same string when reversed.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcbdd&quot;
<strong>Output:</strong> true
<strong>Explanation: </strong>&quot;abcbdd&quot; = &quot;a&quot; + &quot;bcb&quot; + &quot;dd&quot;, and all three substrings are palindromes.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bcbddxy&quot;
<strong>Output:</strong> false
<strong>Explanation: </strong>s cannot be split into 3 palindromes.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code>​​​​​​ consists only of lowercase English letters.</li>
</ul>

class Solution {
public:
    int dp1(string&s,int start,int end,int k,vector<vector<vector<int>>>&dp,vector<vector<int>>&pre){
        if(k==1){
            return pre[start][end];
        }
        if(k==(end-start+1)){
            dp[start][end][k]=0;
            return 0;
        }
        if(dp[start][end][k]!=-1){
            return dp[start][end][k];
        }
        // int min1=s.size();
        // int u1=k-1;
        for(int j=start;j<end;j++){
            int len1=(j-start+1);
            int len2=(end-(j+1)+1);
            for(int u=1;u<k;u++){
                if(u<=len1 && (k-u)<=len2){
                    if(dp1(s,start,j,u,dp,pre) && dp1(s,j+1,end,k-u,dp,pre)){
                        dp[start][end][k]=1;
                        return 1;
                    }
                }
            }
        }
        dp[start][end][k]=0;
        return 0;
    }
    void checkpalin(string&s,vector<vector<int>>&pre,int start,int end){
        int cnt=0;
        while(start>=0 && end<s.size()){
            if(s[start]!=s[end]){
                return ;
            }
            pre[start][end]=1;
            start--;
            end++;
        }
    }
    bool checkPartitioning(string s) {
        vector<vector<int>>pre(s.size(),vector<int>(s.size(),0));
        for(int i=0;i<s.size();i++){
            checkpalin(s,pre,i,i);
            checkpalin(s,pre,i,i+1);
        }
        // vector<vector<vector<int>>>dp(s.size(),vector<vector<int>>(s.size(),vector<int>(4,-1)));
        // if(dp1(s,0,s.size()-1,3,dp,pre)){
        //     return true;
        // }
        // return false;
        for(int i=0;i<s.size()-2;i++){
            for(int j=i+1;j<s.size()-1;j++){
                if(pre[0][i] && pre[i+1][j] && pre[j+1][s.size()-1]){
                    return true;
                }
            }
        }
        return false;
        
    }
};
93476