Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.​​​​​

A string is said to be palindrome if it the same string when reversed.

&nbsp;
Example 1:

Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.


Example 2:

Input: s = "bcbddxy"
Output: false
Explanation: s cannot be split into 3 palindromes.


&nbsp;
Constraints:


	3 &lt;= s.length &lt;= 2000
	s​​​​​​ consists only of lowercase English letters.


class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)

        @lru_cache(None)
        def pal(i,j):
            if i == j:
                return True
            if s[i] != s[j]:
                return False
            if i+1 == j:
                return True
            else:
                return pal(i+1,j-1)

        for i in range(n-2):
            if pal(0,i):
                for j in range(i+1,n-1):
                    if pal(i+1,j) and pal(j+1,n-1):
                        return True
        return False
class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int g=0 ; g<n ; g++){
            for(int i=0, j=g ; j<n ; j++, i++){
                if(g == 0)
                    dp[i][j] = true;
                else if(g == 1)
                    dp[i][j] = (s.charAt(i) == s.charAt(j)) ? true : false;
                else{
                    dp[i][j] = (dp[i+1][j-1]&((s.charAt(i) == s.charAt(j)) ? true : false));
                }
            }
        }
        for(int i=0 ; i<n-2 ; i++){
             if(dp[0][i]){
                for(int j=i+1 ; j<n-1 ; j++){
                    if(dp[i+1][j] && dp[j+1][n-1]){
                        return true;
                    }
                }
             }
        }
        return false;
    }
}
class Solution {
public:
	vector<vector<int>> dp1;
	bool isPalindrome(string& s, int i, int j) {
		if (i >= j) return true;
		if (dp1[i][j] != -1) return dp1[i][j];
		if (s[i] == s[j]) return dp1[i][j] = isPalindrome(s, i + 1, j - 1);
		return dp1[i][j] = false;
	}
	bool checkPartitioning(string s) {
		int n = s.size();
		dp1.resize(n,vector<int> (n,-1));
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n-1;j++){
				if(isPalindrome(s,0,i) && isPalindrome(s,i+1,j) && isPalindrome(s,j+1,n-1))
					return true;
			}
		}
		return false;
	}
};
/**
 * @param {string} s
 * @return {boolean}
 */
var checkPartitioning = function(s) {
    // create a dp that will represent the starting and ending index of a substring
    // if dp[i][j] is true that means that the string starting from i and ending at j is a palindrome
    const dp = new Array(s.length).fill(null).map(() => new Array(s.length).fill(false));
    
    // all substrings of length 1 are palindromes so we mark all matching indices as true
    for (let i = 0; i < s.length; i++) {
        dp[i][i] = true;
    }
    
    
    // slowly grow the substring from each index
    // we will know the substring is a palindrom if the substring prior was a palindrome
    for (let lengthOfSubString = 2; lengthOfSubString <= s.length; lengthOfSubString++) {
        for (let startingIndex = 0; startingIndex + lengthOfSubString <= s.length; startingIndex++) {
            
            // if it's not the same character, then it can not be a palindrome
            if (s[startingIndex] !== s[startingIndex + lengthOfSubString - 1]) continue;
            
            if (lengthOfSubString <= 3 || 
                
                // this checks if the prior substring was a palindrome
                dp[startingIndex + 1][startingIndex + lengthOfSubString - 2]) {
                
                dp[startingIndex][startingIndex + lengthOfSubString - 1] = true;
            }
        }
    }
    
    // find out if any 3 of the partitions are palindromes
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j < s.length; j++) {
            if (dp[0][i] && dp[i + 1][j] && dp[j + 1][s.length - 1]) return true;
        }
    }
    
    // if we haven't found a partition, return false
    return false;
};
Palindrome Partitioning IV