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.
1 public class Solution { 2 public int minCut(String s) { 3 int len = s.length(); 4 int D[] = new int [len+1]; 5 for(int i=0;i<=len;i++){ 6 D[i] = len-i-1; //this means for example: abc cut 2 7 } 8 boolean [][]p = new boolean[len][len]; 9 for(int i=len-1;i>=0;i--){ 10 for(int j=i;j<len;j++){ 11 if(s.charAt(i)==s.charAt(j)&&(j-i<2 ||p[i+1][j-1])){ 12 D[i] = Math.min(D[i],D[j+1]+1); 13 p[i][j] = true; 14 } 15 } 16 } 17 return D[0]; 18 } 19 }