Question:

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.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

二刷

  1. 首先尝试了通过回溯实现这道题，思想应该是对的，但是超时，无法AC。 
    class Solution {
 private int result = Integer.MAX_VALUE;
 public int minCut(String s) {
     if(s == null || s.length() == 0 || s.length() == 1) return 0;
     backtrace(s, 0, 0);
     return result - 1;
 }
 private void backtrace(String s, int res, int index){
     if(index == s.length()){
         result = Math.min(this.result, res);
     }else{
         for(int i = index + 1; i <= s.length(); i++){
             String sub = s.substring(index, i);
             if(isPalindrome(sub)){
                 backtrace(s, res + 1, i);
             }
         }
     }
 }
 private boolean isPalindrome(String s){
     int len = s.length();
     if(len == 0 || len == 1) return true;
     int low = -1, high = len;
     char[] arr = s.toCharArray();
     while(low < high){
         if(++low < len && --high >= 0)
             if(arr[low] != arr[high])
                 return false;
     }
     return true;
 }
}
  2. 使用DP实现这道题，参考了Discussion。 
    class Solution {
 public int minCut(String s) {
     if(s == null || s.length() == 0 || s.length() == 1) return 0;
     int len = s.length();
     // 用于存储从第一个index到第二个index是否是回文的。
     boolean[][] dp = new boolean[len][len];
     int[] cut = new int[len];
     int min = 0;
     char[] arr = s.toCharArray();
     for(int end = 0; end < len; end++){
         min = end;
         for(int start = 0; start <= end; start++){
           // 当首字符和尾字符相同时， 此时我们通过(start + 1 > end - 1)证明当前指向的是某个字符本身，或者其中包含的字符是回文的(dp[start + 1][end - 1])
           // 这就说明从当前的start到end是回文的。
             if(arr[end] == arr[start] && (start + 1 > end - 1 || dp[start + 1][end - 1])){
                 dp[start][end] = true;
                 if(start == 0) min = 0;
                 // 鉴于start到end的字符串是回文的，所以最坏的可能性就是cut[start - 1]（前面的字符串需要分割的最小次数） + 1（为了分割当前的字符串）
                 else min = Math.min(min, cut[start - 1] + 1);
             }
         }
         cut[end] = min;
     }
     return cut[len - 1];
 }
}

Reference

  1. Java DP with my understanding