# 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];
}
};