<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:
  def getIdToPalindomeEndIds(self, s: str) -> Dict:
    id_to_end_ids = {}
    for i in range(len(s)):
      id_to_end_ids[i] = []
      # odd-length palindromes, consecutive characters center
      self.expandPalindromesAroundCenter(s, i, i, id_to_end_ids)
      # even-length palindromes, consecutive characters center
      self.expandPalindromesAroundCenter(s, i, i + 1, id_to_end_ids)
    return id_to_end_ids

  def expandPalindromesAroundCenter(self, ss: str, lo: int, hi: int, id_to_end_ids: Dict):
    while lo >= 0 and hi < len(ss):
      if ss[lo] != ss[hi]:
        break  # the first and last characters don't match!
      id_to_end_ids[lo].append(hi)
      # expand around the center
      lo -= 1
      hi += 1
    return

  def checkPartitioning(self, s: str) -> bool:
    id_to_end_ids = self.getIdToPalindomeEndIds(s)
    n = len(s)
    num_splits = 3
    # // dp[i][j] tracks whether substring s[i:] can be partitioned in to j polindromes.
    dp = [[None] * (num_splits+1) for _ in range(n)]

    def _canParition(i, cur_splits, dp):
      if i >= n and cur_splits == 0:
        return True
      if i >= n or cur_splits == 0:
        return False
      if dp[i][cur_splits] is not None:
        return dp[i][cur_splits]
      can_partition = False
      for j in id_to_end_ids.get(i, []):
        if j == n - 1:
          if cur_splits == 1:
            can_partition = True
        else:
          can_partition = can_partition or _canParition(j+1, cur_splits-1, dp)
        if can_partition:
          break
      dp[i][cur_splits] = can_partition
      return can_partition

    return _canParition(0, num_splits, dp)
809