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.
For example, given s = “aab”, Return 1 since the palindrome partitioning [“aa”,“b”] could be produced using 1 cut.
Solution:
public class Solution {
public int minCut(String s) {
if(s.length()==0) return 0;
int[] dp = new int[s.length()+1];
for(int i=0; i<=s.length(); i++) dp[i] = i-1;
for(int i=2; i<=s.length(); i++){
int l=i, r=i;
while(l>=1 && r<=s.length() && s.charAt(l-1)==s.charAt(r-1)){
dp[r] = Math.min(dp[r], dp[l-1]+1);
l--; r++;
}
l=i-1; r=i;
while(l>=1 && r<=s.length() && s.charAt(l-1)==s.charAt(r-1)){
dp[r] = Math.min(dp[r], dp[l-1]+1);
l--; r++;
}
}
return dp[s.length()];
}
}