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 PalindromePartitioningII { public int minCut(String s){ int n = s.length(); int[] cut = new int[n+1]; for(int i=0;i<=n;i++){ cut[i]=i-1; } for(int i=0;i<n;i++){ //奇数长度的回文 for(int j=0; i-j>=0 && i+j<n && s.charAt(i-j)==s.charAt(i+j);j++){ cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j]); } //偶数长度的回文 for(int j=1; i-j+1>=0 && i+j<n && s.charAt(i-j+1)==s.charAt(i+j);j++){ cut[i+j+1] = Math.min(cut[i+j+1], 1+cut[i-j+1]); } } return cut[n]; } }
