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.
public class Solution { public int minCut(String s) { int n = s.length(); int[] result = new int[n]; boolean[][] palindrome = new boolean[n][n]; for(int i = 0; i < n; i++) { result[i] = i; for(int j = 0; j <= i; j++) { if(s.charAt(i) == s.charAt(j) && (i - j <= 1 || palindrome[j+1][i-1])){ palindrome[j][i] = true; if(j != 0) { result[i] = Math.min(result[i], result[j-1] + 1); } else { result[i] = 0; } } } } return result[n-1]; } }
