<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>

/*

*/

template<typename Fn, 
    typename ... Args, 
    typename return_t = std::invoke_result_t<Fn, Args...>>
return_t memoApply(
    Fn && fn, 
    std::map<std::tuple<std::decay_t<Args>...>, return_t>& memo, 
    Args&&... args)
{
    std::tuple<std::decay_t<Args>...> hashKey = std::make_tuple(std::forward<Args>(args)...);

    auto maybeRes = memo.find(hashKey);
    if(maybeRes != memo.end())
    {
        return maybeRes->second;
    }

    auto res = std::apply(std::forward<Fn>(fn), hashKey);

    memo.insert({hashKey, res});
    return res;
}

class Solution {
private:
    const string *sPtr;
    std::vector<std::vector<std::optional<bool>>> memo;

    bool isPalindrome(size_t startPos, size_t endPos)
    {
        if(memo[startPos][endPos].has_value())
        {
            return *memo[startPos][endPos];
        }
        bool res = [&]()
        {
            if(startPos == endPos)
            {
                return true;
            }
            if(startPos > endPos)
            {
                return false;
            }
            bool tailsAgree = sPtr->at(startPos) == sPtr->at(endPos);

            if(startPos + 1 == endPos)
            {
                return tailsAgree;
            }
            return tailsAgree && isPalindrome(startPos + 1, endPos - 1);
        }();
        memo[startPos][endPos] = res;
        return res;
    }
    bool checkPartitioningImpl(size_t partitionsToMake, size_t startPoint = 0)
    {
        if(partitionsToMake == 1)
        {
            return isPalindrome(startPoint, sPtr->size() - 1);
        }
        for(size_t endPoint = startPoint; endPoint < sPtr->size() - 1; ++endPoint)
        {
            if(isPalindrome(startPoint, endPoint) && checkPartitioningImpl(partitionsToMake - 1, endPoint + 1))
            {
                return true;
            }
        }

        return false;
    }
public:
    bool checkPartitioning(const string& s) {
        sPtr = &s;
        memo = vector<vector<std::optional<bool>>>(s.size(), vector<std::optional<bool>>(s.size(), std::nullopt));

        return checkPartitioningImpl(3);
    }
};
80688