132. Palindrome Partitioning II Leetcode Java

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.

Solution:

Dynamic programming.

First of all, if we know the minimum cut of s.substring(0,i), let's say res[i], then for the minimum cut of s.substring(0,i+1) let's say res[i+1] must be <=res[i]+1. Because a single character(s.charAt(i)) must be a valid palindrome. Further more, if any index between 0 to i (let's say j) can make s.subString(j,i+1) a valid palindrome, then res[i+1]<=res[j-1]+1. So if we search such j between 0 to i, and if this partition can make res[i+1] smaller or lesser, we then update res[i+1] to the smaller one. In this way, we can find the minimum cut for palindrome partition of s.

Tips: Set the cut for s.substring(0,0) as res[0]=-1, this way can avoid to take special care of the case when s.substring(0,i+1) itself is a valid palindrome, then simply set res[i+1]=res[0]+1=0. No cut is needed.

In order to check the valid palindrome more efficient, a dictionary is built upfront use the same method as the previous problem: Palindrome Partitioning 

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