Description:
Given 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.
Examples:
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: 1Solution in Python:
Problem Breakdown
We need to partition the given string s such that each substring in the partition is a palindrome, and we want to minimize the number of cuts required.
Approach
- Dynamic Programming: We’ll use a DP approach to solve this problem efficiently.
- Palindrome Check: We will precompute whether any substring
s[i:j+1]is a palindrome or not using a 2D boolean arrayis_palindrome. - Minimum Cuts Calculation: We will use a 1D array
cutswherecuts[i]represents the minimum cuts needed for the substrings[0:i+1].
Steps
- Initialize the
is_palindromearray:is_palindrome[i][j]isTrueif the substrings[i:j+1]is a palindrome.- To fill this array, we use the property of palindromes: a substring
s[i:j+1]is a palindrome ifs[i] == s[j]ands[i+1:j]is also a palindrome.
- Initialize the
cutsarray:cuts[i]starts asi, which is the maximum number of cuts needed (worst case: every character is a palindrome by itself).
- Update the
cutsarray:- If
s[0:i+1]is a palindrome, then no cut is needed for this substring, socuts[i] = 0. - Otherwise, find the minimum cuts needed by checking all possible previous cuts.
- If
Python
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
# Initialize a 2D array to store palindrome status
is_palindrome = [[False] * n for _ in range(n)]
# Every single character is a palindrome
for i in range(n):
is_palindrome[i][i] = True
# Fill the is_palindrome table
for length in range(2, n + 1): # length of the substring
for start in range(n - length + 1):
end = start + length - 1
if length == 2:
is_palindrome[start][end] = (s[start] == s[end])
else:
is_palindrome[start][end] = (s[start] == s[end] and is_palindrome[start + 1][end - 1])
# Initialize the cuts array
cuts = [0] * n
for i in range(n):
# If the whole substring s[0:i+1] is a palindrome, no cut is needed
if is_palindrome[0][i]:
cuts[i] = 0
else:
# Set initial cuts[i] to the maximum possible cuts (cut before every character)
cuts[i] = i
for j in range(1, i + 1):
if is_palindrome[j][i]:
cuts[i] = min(cuts[i], cuts[j - 1] + 1)
return cuts[n - 1]Explanation
- Palindrome Table Initialization:
- We first assume that every single character is a palindrome.
- We then check substrings of length 2 and above to update the palindrome status in the
is_palindrometable.
- Cuts Calculation:
- We check for each substring if it’s a palindrome from the beginning. If it is, no cut is needed.
- Otherwise, for each substring, we find the minimum cuts needed by checking possible positions for previous cuts where the substring could be divided into palindromes.
This approach ensures that we efficiently compute the minimum cuts needed for palindrome partitioning using dynamic programming.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
const n = s.length;
// Initialize a 2D array to store palindrome status
const isPalindrome = Array.from({ length: n }, () => Array(n).fill(false));
// Every single character is a palindrome
for (let i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
// Fill the isPalindrome table
for (let length = 2; length <= n; length++) { // length of the substring
for (let start = 0; start <= n - length; start++) {
const end = start + length - 1;
if (length == 2) {
isPalindrome[start][end] = (s[start] === s[end]);
} else {
isPalindrome[start][end] = (s[start] === s[end] && isPalindrome[start + 1][end - 1]);
}
}
}
// Initialize the cuts array
const cuts = Array(n).fill(0);
for (let i = 0; i < n; i++) {
// If the whole substring s[0:i+1] is a palindrome, no cut is needed
if (isPalindrome[0][i]) {
cuts[i] = 0;
} else {
// Set initial cuts[i] to the maximum possible cuts (cut before every character)
cuts[i] = i;
for (let j = 1; j <= i; j++) {
if (isPalindrome[j][i]) {
cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
}
}
}
}
return cuts[n - 1];
};Solution in Java:
Java
class Solution {
public int minCut(String s) {
int n = s.length();
// Initialize a 2D array to store palindrome status
boolean[][] isPalindrome = new boolean[n][n];
// Every single character is a palindrome
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
// Fill the isPalindrome table
for (int length = 2; length <= n; length++) { // length of the substring
for (int start = 0; start <= n - length; start++) {
int end = start + length - 1;
if (length == 2) {
isPalindrome[start][end] = (s.charAt(start) == s.charAt(end));
} else {
isPalindrome[start][end] = (s.charAt(start) == s.charAt(end) && isPalindrome[start + 1][end - 1]);
}
}
}
// Initialize the cuts array
int[] cuts = new int[n];
for (int i = 0; i < n; i++) {
// If the whole substring s[0:i+1] is a palindrome, no cut is needed
if (isPalindrome[0][i]) {
cuts[i] = 0;
} else {
// Set initial cuts[i] to the maximum possible cuts (cut before every character)
cuts[i] = i;
for (int j = 1; j <= i; j++) {
if (isPalindrome[j][i]) {
cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
}
}
}
}
return cuts[n - 1];
}
}Solution in C#:
C#
public class Solution {
public int MinCut(string s) {
int n = s.Length;
// Initialize a 2D array to store palindrome status
bool[,] isPalindrome = new bool[n, n];
// Every single character is a palindrome
for (int i = 0; i < n; i++) {
isPalindrome[i, i] = true;
}
// Fill the isPalindrome table
for (int length = 2; length <= n; length++) { // length of the substring
for (int start = 0; start <= n - length; start++) {
int end = start + length - 1;
if (length == 2) {
isPalindrome[start, end] = (s[start] == s[end]);
} else {
isPalindrome[start, end] = (s[start] == s[end] && isPalindrome[start + 1, end - 1]);
}
}
}
// Initialize the cuts array
int[] cuts = new int[n];
for (int i = 0; i < n; i++) {
// If the whole substring s[0:i+1] is a palindrome, no cut is needed
if (isPalindrome[0, i]) {
cuts[i] = 0;
} else {
// Set initial cuts[i] to the maximum possible cuts (cut before every character)
cuts[i] = i;
for (int j = 1; j <= i; j++) {
if (isPalindrome[j, i]) {
cuts[i] = Math.Min(cuts[i], cuts[j - 1] + 1);
}
}
}
}
return cuts[n - 1];
}
}