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.
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 <= 2000 s consists of lower-case English letters only.
class Solution {
public int minCut(String s) {
boolean[][] isPal=computePalindromes(s);
if(isPal[0][s.length()-1]) return 0;
int cuts[]=new int[s.length()];
/*
Role of the following loop: With outer loop we are selecting a letter and then we compare it with each letter before it
and see if we need to make a cut or not. consider "aab"
we are on second 'a' with outer loop
so when inner loop runs we check if aa is palindrome or not. If yes, then we check if j==0 if that's the case then we
don't need to make any cut there. So we don't make any cut there but if we arent' on start then we have to make a cut here
so total cuts would be cuts[j-1] +1 which is nothing but cuts done before this cut + 1
*/
for(int i=0;i<s.length();i++){
int min=i;
for(int j=0;j<=i;j++){
if(isPal[j][i]){
min=j==0?0:Math.min(min,cuts[j-1]+1);
}
}
cuts[i]=min;
}
return cuts[cuts.length-1];
}
public boolean[][] computePalindromes(String s){
boolean[][] res=new boolean[s.length()][s.length()];
for(int i=0;i<s.length();i++){
for(int j=0;j<=i;j++){
if(s.charAt(j)==s.charAt(i) && (j+1>i-1 || res[j+1][i-1]))
res[j][i]=true;
}
}
return res;
}
}