Problem statement

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

Solution

Let us do the following steps:

  1. Generate all possible palindromes, we can do it in O(n^2) time: consider all 2n-1 possible middles and then extend around them until we can. Dictionary d[i] will keep all palindromes which start with place i.
  2. dp(i) is number of minimum palindromes for string s[:i]. Then to calculate dp(i) we need to calculate dp(k-1) + 1 for all k <= i and such that i in d[k], this means that s[k:i+1]` is palindrome; then we need to choose the minimum among all these candidates.

Complexity

Time complexity is O(n^2) to generate all palindromes and O(n^2) to evaluate all dp values, so overall time complexity is O(n^2). Space complexity is O(n^2) as well.

Code

class Solution:
    def minCut(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):
            if i == -1: return -1
            return min([dp(k-1) + 1 for k in range(0, i+1) if i in d[k]])
        
        return dp(n-1)