# Palindrom Partition

Given a string s, we can partition s such that every segment is a palindrome (e.g, ‘abba’ is a palindrome, ‘a’ is a palindrome, ‘ab’ is not). Please write a function to return the minimum cuts needed for a palindrome parti“tioning, given string s.

## Solution

``````a b a b b b a b b a b a
i             n
``````

``````a   b   a   b   b   b   a   b   b   a   b   a
i               j  j+1      n
``````

D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,

D[i] = min(1+D[j+1] ) i<=j <n

isPalindrome( i , j ) = (value(i) == value(j)) AND ( isPalindrome(i+1, j-1) OR j – i <= 1 ) ， i和j分别表示substring的首坐标和尾坐标。

minCut(i) = min(minCut[j+1]+1, minCut[i])，for i <= j < n, and substring(i , j) is palindrome。

## Code

``````int palindromePartition(String str){
boolean[][] flag = new boolean[str.length()][str.length()];
int[] dp = new int[str.length() + 1];
for (int i = 0; i < dp.length; i++){
dp[i] = dp.length - i - 1;
}

for (int i = str.length() - 1; i >= 0; i--){
for (int j = i; j < str.length(); j++){
if ((str.charAt(i) == str.charAt(j) && ((j-i < 2) || flag[i+1][j-1])){
flag[i][j] = true;
dp[i] = Math.min(dp[j+1]+1, dp[i]);
}
}
}
return dp[0];
}
``````