Palindrome Partitioning II

Q: 
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.

A:
Dynamic programming. (quite similar to Matrix - chain problem)

public class PalindromePartitioningII {
 public int minCut(String s) {
  int n = s.length();
  if (n == 0)
   return 0;
  // use an matrix to record if a subString of s is palindrome.
  boolean[][] isPalindromeArray = new boolean[n][n]; // record only i<=j
  buildPalindromeArray(s, isPalindromeArray);

  // for each just added s[i], record which minimum cut for s[0....i],
  // and its number
  int[] minCutNum = new int[n + 1]; // minCutNum[i] means the after the
           // ith position
  minCutNum[0] = -1;

  // add each char from the front to end
  for (int j = 1; j <= n; j++) {
   minCutNum[j] = minCutNum[j - 1] + 1;
   // now we combine the suffix part, with s.charAt(i)
   for (int i = j - 1; i >= 1; i--) {
    if (isPalindromeArray[i - 1][j - 1]) {// if substring s[i-1, ...
              // ,j-1] is palindrome
     minCutNum[j] = Math.min(minCutNum[j], 1 + minCutNum[i - 1]);
    }
   }
  }
  return minCutNum[n];
 }

 private void buildPalindromeArray(String s, boolean[][] isPalindromeArray) {
  // following matrixly calling method is too time consuming, because of
  // the repeated calling the function
  // Solution : using the dynamic programming philosophy.
  // using the small edge to build the long edge
  // for (int i = 0; i < n; i++) {
  // for (int j = i + 1; j < n; j++) {
  // isPalindromeArray[i][j] = isPalindrome(s.substring(i, j + 1));
  // }
  // }
  for (boolean[] row : isPalindromeArray)
   Arrays.fill(row, true); // initialize the row as TRUE,
  // for substring length of i=j, means one character, it is already set
  // to zeros
  for (int len = 1; len < s.length(); len++) { // here , length = j - i
   int j; // j is the end point of a substring
   for (int i = 0; i < s.length() - len; i++) {
    j = i + len;
    isPalindromeArray[i][j] = (s.charAt(i) == s.charAt(j) && isPalindromeArray[i + 1][j - 1]);
   }
  }
 }
}

上面这个想法，还是挺SB的，毕竟要n^2的空间。   到底是自己做的第二道leetcode 的题目啊。

新想法如下，有一个链表数组： 对每个位置， 有该位置可以与previous position  构成 palindrome 的位置的信息
另外加一个minCut[] 来记录对每一个地址，其number of minimum cut.

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        int[] minCut = new int[ n ];
        List<List<Integer>> paliPos = new ArrayList<>();
        for(int i =0;i<n;i++){
            List<Integer> al = new ArrayList<>();
            al.add(i);
            paliPos.add(al);
        }
        for(int i=1;i<n;i++){
            char ch = s.charAt(i);
            minCut[i] = 1 + minCut[i-1];
            if(ch == s.charAt(i-1) ){ // direct match with the left
                minCut[i] = Math.min(minCut[i],  (i==1) ? 0: 1+minCut[i-2] );
                paliPos.get(i).add(i-1);
            }
            List<Integer> leftPosList = paliPos.get(i-1);
            for(int pos : leftPosList){
                if(pos>0 && s.charAt(pos-1) == ch){
                    paliPos.get(i).add(pos-1);
                    minCut[i] = Math.min( minCut[i], pos ==1 ? 0 : 1 + minCut[pos-2] );
                }
            }
        }
        return minCut[n-1];
    }
}

-----------------------------思路1 的重新实现  （第二遍做的）--------------------------------------

public class Solution {
     public int minCut(String s) {
        if(s.length()<=1 )
            return 0;
        // build a 2D array, indicating whether each [i,j] position makes an palindrome
        int n = s.length();
        boolean[][] isPalin = new boolean[n][n];
        //build the whole set
             for(int j =0;j<n;j++){
                isPalin[j][j] = true;  //set [i][i] == true
                for(int i = j-1; i>=0; i--){
                    isPalin[i][j] = s.charAt(i)==s.charAt(j) 
     &&( isPalin[i+1][j-1] || i+1 == j);
                }
            }
        // build a minCut from begining to end
        int[] minCut = new int[n];
        for(int i =1;i<n;i++){
            minCut[i] = minCut[i-1] +1;
            //check all its previous mathing
            for(int j = 0;j<i;j++){
                if(isPalin[j][i] == true){
                    if(j ==0){
                        minCut[i] = 0;
                    }else{ // coz we gonna use j-1 as index
                        minCut[i] = Math.min(minCut[j-1] +1,minCut[i]);
                    }
                }
            }
        }
         return minCut[n-1];
     }
}

（呵呵，看来，做题还是有进步的。╮(╯▽╰)╭    刚开始，光晕去了）

 Mistakes:
1: when input string is too large, still declaring the isPalindromeArray[n][n] is too time comsuming  
 2: when building MatchPos ArrayList, I forget the case that the char at i_th position could be matched directly with one single ahead.
例如： aab，  得到的list 应该是[0][0,1][0,1,2]
 因此要测试， i 和i-1的匹配（ 在  如果两个紧挨着， 就无法分出preMatch来了

3: 2遍： 在建立2D isPalindrome array的时候，应该从 没加入一个字符， 基于 其前面所有的match 的情况已经计算出来。
因此， for (j =0, j< n;j++)
                   for ( i =j-1;i >=0;i--)
4:  2遍;  在基于之前的计算的时候， 要考虑，前面的是否存在，  亦即 i ==j-1的时候。

Learned: 
TPTP 等分析代码运行时间的插件都不能用。  还是用最简单的 打印出各自运行的时间就行。

 
long beginTime = System.nanoTime();

        System.out.println(（System.nanoTime() - beginTime）/10000);

        beginTime = System.nanoTime();

然后，每次upddate beginTime, 对比就行。 System.currentTimeMillis vs System.nanoTime  都是返回long类型，但是区别呢？？？

2: Arrays.fill() 函数，只能对一维数组填充。 多维的，要自己去一维得填 （可以利用Arrays.fill() 函数）

2: 如果是在eclipse中运行，需要import 一些库，例如import java.util.*;


别人的解法：（但基本上，还是自己的最好，不用判断回文的函数。）
有一个是利用DFS回溯的。调用O(n^2) 次dfs， 貌似不太好。

-----------------------------利用递归调用，每次取后面的----------