Problem statement

https://leetcode.com/problems/palindrome-partitioning-iv/

Solution 1

Function helper here will create all possible palindromes: it will work in O(n^2) time with early breaks. Then what we can do is to check all palindromes start with 0-th element and all palindromes which end with n-1 the elemen and check if the string in the middle is palindrome as well.

Complexity

Time is O(n^2), space as well.

Code

class Solution:
    def checkPartitioning(self, s):
        d1, d2, n = defaultdict(set), defaultdict(set), len(s)
        
        def helper(i, j):
            while i >= 0 and j < n and s[i] == s[j]:
                d1[i].add(j)
                d2[j].add(i)
                i, j = i - 1, j + 1
        
        for k in range(n):
            helper(k, k)
            helper(k, k + 1)
            
        for i in d1[0]:
            for j in d2[n-1]:
                if j-1 in d1[i+1]: return True
                
        return False

Solution 2

There is a bit slower but more universal approach: we again generate all palindromes, but then we use function dp(i, k), which will answer the question can string s[i:] be separated into k palindromes.

Complexity

It is also O(n^2) for both time and space but works slower

Code

class Solution:
    def checkPartitioning(self, s):
        d, n = defaultdict(set), len(s)
        
        def helper(i, j):
            while i >= 0 and j < n and s[i] == s[j]:
                d[i].add(j)
                i, j = i - 1, j + 1
        
        for k in range(n):
            helper(k, k)
            helper(k, k + 1)
            
        @lru_cache(None)
        def dp(i, k): 
            if k < 0: return False 
            if i == n: return k == 0
            return any(dp(j+1, k-1) for j in d[i])
        
        return dp(0, 3)