Algorithm
Problem Name: 132. Palindrome Partitioning II
Given a string s, partition s such that every substringof the partition is a palindrome
Return the minimum cuts needed for a palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a" Output: 0
Example 3:
Input: s = "ab" Output: 1
Constraints:
1 <= s.length <= 2000sconsists of lowercase English letters only.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int _min(int a, int b) {
return a < b ? a : b;
}
int minCut(char* s) {
int *dp, n, i, k;
n = strlen(s);
dp = malloc((n + 1) * sizeof(int)); // number of cuts on length
//assert(dp);
dp[0] = -1;
for (i = 0; i < n; i ++) {
dp[i + 1] = dp[i] + 1;
}
for (i = 0; i < n; i ++) {
dp[i + 1] = _min(dp[i + 1], dp[i] + 1);
for (k = 1; // "aba"
i - k >= 0 &&
i + k < n &&
s[i - k] == s[i + k];
k ++) {
dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k] + 1);
}
for (k = 1; // "aaaa"
i - k + 1 >= 0 &&
i + k < n &&
s[i - k + 1] == s[i + k];
k ++) {
dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k + 1] + 1);
}
}
i = dp[n];
free(dp);
return i;
}
Input
s = "aab"
Output
1
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;
class Solution {
public:
int minCut(string s) {
int n = s.length();
if (n == 0) return 0;
vector<int> dp(n);
vector < vector<int> > mem(n, vector<int>(n)); // memorization for palindrome
int i, j, k;
// build palindrome table
for (i = 0; i < n; i++) {
mem[i][i] = 1;
j = i, k = i + 1; // even length
while(j >= 0 && k < = n - 1) {
if (s[j] != s[k]) break;
mem[j][k] = 1;
j--;
k++;
}
j = i - 1, k = i + 1; // odd length
while(j >= 0 && k < = n - 1) {
if (s[j] != s[k]) break;
mem[j][k] = 1;
j--;
k++;
}
}
// run dynamic programming
dp[0] = 0;
for (i = 1; i < n; i++) {
if (mem[0][i]) {
dp[i] = 0;
}
else {
int min = dp[i - 1] + 1;
for (j = 0; j < i; j++) {
if (mem[j + 1][i] && dp[j] + 1 < min) {// if right half is palindrome
min = dp[j] + 1;
}
}
dp[i] = min;
}
}
return dp[n - 1];
}
};
int main() {
string str0 = "aababa";
string str1 = "ababa";
Solution s;
assert(s.minCut(str0) == 1);
assert(s.minCut(str1) == 0);
printf("all tests passed!\n");
return 0;
}
Input
s = "aab"
Output
1
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const minCut = function(s) {
const n = s.length
if (n <= 1) return 0
const dp = new Array(n).fill(0)
for (let i = 1; i < n; i++) dp[i] = i
for (let i = 1; i < n; i++) {
// odd
for (
let start = i, end = i;
end < n && start >= 0 && s[end] === s[start];
start--, end++
) {
dp[end] = Math.min(dp[end], start === 0 ? 0 : dp[start - 1] + 1)
}
// even
for (
let start = i - 1, end = i;
end < n && start >= 0 && s[end] === s[start];
start--, end++
) {
dp[end] = Math.min(dp[end], start === 0 ? 0 : dp[start - 1] + 1)
}
}
return dp[n - 1]
}Input
s = "a"
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minCut(self, s):
q, pal, used = [(0, 0)], collections.defaultdict(list), {(0, 0)}
for i in range(len(s)):
for j in range(i, len(s)):
if s[i:j + 1] == s[i:j + 1][::-1]: pal[i].append(j + 1)
while q:
cuts, i = heapq.heappop(q)
i *= -1
if i == len(s): return cuts - 1
for j in pal[i]:
if (cuts + 1, -j) not in used:
used.add((cuts + 1, -j))
heapq.heappush(q, (cuts + 1, -j))
Input
s = "a"