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

"""
問是否可以把s切成3段non-empty palindrome substring

intuition 1: 先做is_palindrome matrix, 然後尋找各種切三段的方式看能不能切出三段都是palindrome

error case: 
    - juchzcedhfesefhdeczhcujzzvbmoeombv: 一開始建立is_palindrome的時候要用substring長度由短掃到長
    
intuition 2: 不做is_palindrome matrix, 直接用 cached is_palindrome(self, i, j) 
    - 如果要用cache function的話不能用inner function
        It does not work as intended because the inner_function gets redefined each time partially_cached is called, 
        and so is the cached version. So each cached version gets called only once.
    - cache有效, 但還是比 intuition 1的matrix要慢
    
"""


class Solution: # 先做is_palindrome matrix再切三段

    # @cache
    def valid_palindrome(self, i, j):
        return self.is_palindrome[i][j]
        # n = len(self.s)
        # s = self.s
        # # print(f"{s=}")
        # def within_boundary(i):
        #     return 0 <= i < n

        # if not within_boundary(i) or not within_boundary(j):
        #     return False
        # if i == j:
        #     return True
        # if j == i + 1 and s[i] == s[j]:
        #     return True
        # if j > (i + 1) and s[i] == s[j] and within_boundary(i + 1) and within_boundary(j - 1):
        #     return self.valid_palindrome(i + 1, j - 1)
        # return False

    def checkPartitioning(self, s: str) -> bool:
        self.s = s
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]
        self.is_palindrome = is_palindrome

        for i in range(n):
            is_palindrome[i][i] = True
        for i in range(1, n):
            if s[i] == s[i - 1]:
                is_palindrome[i - 1][i] = True
        for length in range(2, n):
            # for j in range(i + 2, n): 這樣填的順序是錯的
            for i in range(n):
                j = i + length
                if j > n - 1:
                    continue
                if s[i] == s[j]:
                    is_palindrome[i][j] = is_palindrome[i + 1][j - 1]
                
        for i in range(n - 2): # i = 第一段結尾, 注意i最大只能到n - 3
            if not self.valid_palindrome(0, i):
                continue
            for j in range(i + 1, n - 1): # j = 第二段結尾, 注意j最大只能到n - 2              
                if self.valid_palindrome(i + 1, j) and self.valid_palindrome(j + 1, n - 1):
                    return True
        return False

                    

2546