## # 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)
{
{
int tail = head + len - 1;
else
}
}
int cut[n];
for (int tail = 0; tail < n; ++tail)
{
cut[tail] = tail;
{
{
cut[tail] = std::min(cut[tail],
}
}
}
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;
{
{
cut[tail] = std::min(cut[tail],
}
}
}
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 tail = mid + off;
while (head >= 0 && tail < n && s[head] == s[tail])
{
cut[tail] = std::min(cut[tail],