Palindrome Partitioning III

Intuition

This is typically a dynamic programming problem with 2 dimensional (one is the string length and another is the k).

Let's say, to split s[:hi + 1] into k palindrome strings, we need at least change dp(hi, k) characters. Then, dp(hi, k) = min( dp(i, k - 1) for i in range(k - 2, hi) ).

One difficult part is the range for i is from k - 2 to hi, this is because k < hi + 1.

Solution


class Solution:
    def numChanges(self, lo, hi):
        count = 0
        while hi > lo:
            if self.s[hi] != self.s[lo]:
                count += 1
            hi -= 1
            lo += 1
        return count

    def dp(self, hi, k):
        if self.cache[hi][k] is None:
            if k == 1:
                self.cache[hi][k] = self.numChanges(0, hi)
            else:
                self.cache[hi][k] = min(
                    [(self.dp(i, k - 1) + self.numChanges(i + 1, hi)) for i in range(k - 2, hi)]
                )
        return self.cache[hi][k]

    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        self.cache = [[None] * (k + 1) for _ in range(n)]
        self.s = s
        return self.dp(n - 1, k)