132. Palindrome Partitioning II
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.
Constraints
Approach
Links
GeeksforGeeks
Examples
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa", "b"] could be produced using 1 cut.
Input: s = "a"
Output: 0
Input: s = "ab"
Output: 1
Solutions
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int minCut(String s) {
if(s == null || s.length() <= 1) return 0;
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
int[] cut = new int[n];
for(int i = 1; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) &&
(i <= j+1 || isPalindrome[i-1][j+1])) {
isPalindrome[i][j] = true;
if(j == 0) {
min = Math.min(min, 0);
} else {
min = Math.min(min, 1+cut[j-1]);
}
}
}
cut[i] = min;
}
return cut[n-1];
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int minCut(String s) {
if(s == null || s.length() <= 1) return 0;
int n = s.length();
int[] dp = new int[n];
char[] sChars = s.toCharArray();
Arrays.fill(dp, n-1);
for(int i = 0; i < n; i++) {
isPalindrome(sChars, i, i, dp);
isPalindrome(sChars, i, i+1, dp);
}
return dp[n-1];
}
private void isPalindrome(char[] sChars, int left, int right, int[] dp) {
while(left >= 0 &&
right < sChars.length &&
sChars[left] == sChars[right]) {
dp[right] = Math.min(dp[right], (left == 0)? 0: 1+dp[left-1]);
left--;
right++;
}
}
}Follow up
Last updated
Was this helpful?