1
# Runtime: 4163 ms (Top 80.92%) | Memory: 673.9 MB (Top 5.26%)
2
class Solution:
3
    def checkPartitioning(self, s: str) -> bool:
4
        n = len(s)
5

6
        @lru_cache(None)
7
        def pal(i, j):
8
            if i == j:
9
                return True
10
            if s[i] != s[j]:
11
                return False
12
            if i + 1 == j:
13
                return True
14
            else:
15
                return pal(i + 1, j - 1)
16

17
        for i in range(n - 2):
18
            if pal(0, i):
19
                for j in range(i + 1, n - 1):
20
                    if pal(i + 1, j) and pal(j + 1, n - 1):
21
                        return True
22
        return False