# 132. Palindrome Partitioning II

CGiven a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

# Solution

Approach 1: DP -- O(N^2). Let table[i] be the min cut for string s[0:i+1], and table[i] = min(table[j-1] + 1) where j from 0 to i+1 and s[j:i+1] is a palindrome. Deciding s[j:i+1] is palindrome can be done in constant time either precalculating all pairs, or embbed into the DP loops.

Approach 2: DP -- O(N^2). Table[i] still stores the min cut, but fill in the table by searching for palindromes by extending from a center to both sides.

# Code (Python)

Approach 1:

    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        # acceleration
        if s == s[::-1]: 
            return 0
        for i in range(1, len(s)):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1
        
        is_palindrome = {}
        for i in range(len(s)):
            for j in range(i):
                if i == j:
                    is_palindrome[(j, i)] = True
                else:
                    is_palindrome[(j, i)] = False
        table = [i for i in range(len(s))]
        for i in range(1, len(s)):
            for j in range(i, -1, -1): # j from i to 0 inclusive -- start close to i
                if s[i] == s[j] and (i - j < 2 or is_palindrome[(j+1, i-1)]):
                    is_palindrome[(j, i)] = True
                    table[i] = min(table[i], table[j-1] + 1) if j > 0 else 0
        return table[-1]

Approach 2:

    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        # acceleration
        if s == s[::-1]: 
            return 0
        for i in range(1, len(s)):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1

        table = [i for i in range(-1, len(s))]
        for i in range(len(s)):
            r1, r2 = 0, 0
            # odd-lengthed palindrome with radius r1
            while i-r1 >= 0 and i+r1 < len(s) and s[i-r1] == s[i+r1]:
                table[i+r1+1] = min(table[i+r1+1], table[i-r1]+1)
                r1 += 1
            # even-lengthed palindrome with radius r2
            while i-r2 >= 0 and i+r2+1 < len(s) and s[i-r2] == s[i+r2+1]:
                table[i+r2+2] = min(table[i+r2+2], table[i-r2]+1)
                r2 += 1
        return table[-1]

# Code (C++)

Approach 1:

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if (n == 0)
            return 0;
        bool isPalindrome[n][n];
        for (int len = 1; len <= n; ++len)
        {
            for (int head = 0; head + len <= n; ++head)
            {
                int tail = head + len - 1;
                if (s[head] == s[tail] && (head+1 >= tail || isPalindrome[head+1][tail-1]))
                    isPalindrome[head][tail] = true;
                else
                    isPalindrome[head][tail] = false;
            }
        }
        int cut[n];
        for (int tail = 0; tail < n; ++tail)
        {
            cut[tail] = tail;
            for (int head = 0; head <= tail; ++head)
            {
                if (isPalindrome[head][tail])
                {
                    cut[tail] = std::min(cut[tail],
                        (head == 0) ? 0 : cut[head-1] + 1);
                }
            }
        }
        return cut[n-1];
    }
};

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if (n == 0)
            return 0;
        bool isPalindrome[n][n];
        int cut[n];
        for (int tail = 0; tail < n; ++tail)
        {
            cut[tail] = tail;
            for (int head = 0; head <= tail; ++head)
            {
                isPalindrome[head][tail] = false;
                if (s[head] == s[tail] && (head + 1 >= tail || isPalindrome[head+1][tail-1]))
                {
                    isPalindrome[head][tail] = true;
                    cut[tail] = std::min(cut[tail],
                        (head == 0) ? 0 : cut[head-1] + 1);
                }
            }
        }
        return cut[n-1];
    }
};

Approach 2:

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if (n == 0)
            return 0;
        int cut[n];
        for (int i = 0; i < n; ++i)
        {
            cut[i] = i;
        }
        for (int mid = 0; mid < n; ++mid)
        {
            for (int off = 0; off < 2; ++off) // O(1).
            {
                int head = mid;
                int tail = mid + off;
                while (head >= 0 && tail < n && s[head] == s[tail])
                {
                    cut[tail] = std::min(cut[tail],
                        (head == 0) ? 0 : cut[head-1] + 1);
                    head--;
                    tail++;
                }
            }
        }
        return cut[n-1];
    }
};