public int minCut(String s){
  if (s == null || s.length() == 0)   return 0;
  int len=s.length();
  int[] cuts=new int[len + 1];
  for (int i=0; i <= len; i++)   cuts[i]=i - 1;
  for (int i=0; i < len; i++) {
    for (int j=0; i - j >= 0 && i + j < len && s.charAt(i - j) == s.charAt(i + j); j++)     cuts[i + j + 1]=Math.min(cuts[i + j + 1],1 + cuts[i - j]);
    for (int j=1; i - j + 1 >= 0 && i + j < len && s.charAt(i - j + 1) == s.charAt(i + j); j++)     cuts[i + j + 1]=Math.min(cuts[i + j + 1],1 + cuts[i - j + 1]);
  }
  return cuts[len];
}

public int minCut ( String s ) { if ( s == null || s . length ( ) == 0 ) return 0 ; int len = s . length ( ) ; int [ ] cuts = new int [ len + 1 ] ; for ( int i = 0 ; i <= len ; i ++ ) cuts [ i ] = i - 1 ; for ( int i = 0 ; i < len ; i ++ ) { for ( int j = 0 ; i - j >= 0 && i + j < len && s . charAt ( i - j ) == s . charAt ( i + j ) ; j ++ ) cuts [ i + j + 1 ] = Math . min ( cuts [ i + j + 1 ] , 1 + cuts [ i - j ] ) ; for ( int j = 1 ; i - j + 1 >= 0 && i + j < len && s . charAt ( i - j + 1 ) == s . charAt ( i + j ) ; j ++ ) cuts [ i + j + 1 ] = Math . min ( cuts [ i + j + 1 ] , 1 + cuts [ i - j + 1 ] ) ; } return cuts [ len ] ; }
each cut at i + j is calculated by scanning ( i - j ) ' s minimum cut + 1 if s [ i - j , i + j ] is a palindrome .
