分割成回文需要的最小分割数 Palindrome Partitioning II @LeetCode

两个DP，用DFS肯定通不过。

参考：http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html

Analysis:
This is a DP problem! Also it is a double DP problem!
Why? Because, if we use the same algorithm in thePalindrome Partitioning I, definitely it will expire the time limit. When you are facing the problem asking "return the minimum/maximum, best, shortest...", it is also a good direction targeting the DP (sometimes greedy also works fine). If you are not familiar with DP problem,hereis a very good reading from topcoder. Generally speaking, DP is not very easy, andmost of the company interviews will NOT cover the DP, so don't worry too much.

For this problem, firstly we consider the main part.
It is a good way to look for the "state", and the "optimal solution" based on that state, to solve the DP problem. In other words, if you found the correct state, and the function of the state representing the optimal solution, all you need is some loops and initialization implementing the algorithm.

Here the state is not too hard ---- minimum cut. Define res[i] = the minimum cut from 0 to i in the string.
The result w =e need eventually is res[s.size()-1].
We know res[0]=0. Next we are looking for the optimal solution function f.
For example, let s = "leet".
f(0) = 0; // minimum cut of str[0:0]="l", which is a palindrome, so not cut is needed.
f(1) = 1; // str[0:1]="le" How to get 1?
f(1) might be: (1) f(0)+1=1, the minimum cut before plus the current char.
(2) 0, if str[0:1] is a palindrome (here "le" is not )
f(2) = 1; // str[0:2] = "lee" How to get 2?
f(2) might be: (1) f(1) + 1=2
(2) 0, if str[0:2] is a palindrome (here "lee" is not)
(3) f(0)+ 1, if str[1:2] is a palindrome, yes!
f(3) = 2; // str[0:3] = "leet" How to get 2?
f(3) might be: (1) f(2)+ 1=2
(2) 0, if str[0:3] is a palindrome (here "leet" is not)
(3) f(0)+ 1, if str[1:3] is a palindrome (here "eet" is not)
(4) f(1)+ 1, if str[2:e] is a palindrome (here "et" is not)
OK, output f(3) =2 as the result.

So, the optimal function is:

f(i) = min [ f(j)+1, j=0..i-1 and str[j:i] is palindrome
0, if str[0,i] is palindrome ]

The above algorithm works well for the smaller test cases, however for the big cases, it still cannot pass.
Why? The way we test the palindrome is time-consuming.

Also using the similar DP idea, we can construct the look-up table before the main part above, so that the palindrome testing becomes the looking up operation. The way we construct the table is also the idea of DP.
e.g. mp[i][j]==true if str[i:j] is palindrome.
mp[i][i]=true;
mp[i][j] = true if str[i]==str[j] and (mp[i+1][j-1]==true or j-i<2 ) j-i<2 ensures the array boundary.

So, using this scheme to test the palindrome helps improve the efficiency and thus we can pass all the test cases. Details see the code below.

package Level5;

import java.util.ArrayList;
import java.util.Hashtable;

/**
Palindrome Partitioning II 

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 S139 {

	public static void main(String[] args) {
		System.out.println(minCut("a"));
	}
	
	// 两个DP
	public static int minCut(String s) {
		int len = s.length();
		
		// minCuts[i]: s[0,i]最小需要的切割数才能使每个子段都是回文
		int[] minCuts = new int[len];
		
		//isPld[i][j]:true 当且仅当子串s[i...j]是回文时
		boolean[][] isPld = new boolean[len][len];

		// 生成isPld[][] 
		// isPld[i][j] = true if s[i]==s[j] and (isPld[i+1][j-1]==true or j-i<2 )  j-i<2: 当只有1位字符串时肯定是回文
		// 根据递推关系,要从左下向右上推导
		for(int i=len-1; i>=0; i--){	// 从下往上 i：起始下标
			for(int j=0; j<len; j++){	// 从左往右 j：结尾下标
				// 是回文 当且仅当 头尾字符相同，且中间也是回文
				if((s.charAt(i)==s.charAt(j)) && (j-i<2 || isPld[i+1][j-1])){
					isPld[i][j] = true;
				}else{
					isPld[i][j] = false;
				}
			}
		}
		
		// 生成minCuts[]
		for(int i=0; i<len; i++){	// 长度为i的字串s[0,i]
			int mc = len;
			if(isPld[0][i]){		// 本身就是回文，因此无需切割
				minCuts[i] = 0;
			}else{
				for(int j=0; j<i; j++){	// 遍历切割，s[0,1]+s[2,i]; s[0,2]+s[3,i]; s[0,3]+s[4,i] ... s[0,i-1]+s[i,i]
					if(isPld[j+1][i]){	// 如果后半段是回文
						mc = Math.min(mc, minCuts[j] + 1);
					}
				}
				minCuts[i] = mc;
			}
		}
		return minCuts[len-1];
	}
	
	
	
	// TLE 基于DFS
	public static int minCut2(String s) {
		ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
		ArrayList<String> al = new ArrayList<String>();
		Hashtable<String, Boolean> ht = new Hashtable<String, Boolean>();
		int[] min = {Integer.MAX_VALUE};
		dfs(s, 0, ht, ret, al, 0, min);
		return min[0];
    }
	
	public static void dfs(String s, int start, Hashtable<String, Boolean> ht, ArrayList<ArrayList<String>> ret, ArrayList<String> al, int cnt, int[] min){
		if(start == s.length()){
			ret.add(new ArrayList<String>(al));
			min[0] = Math.min(min[0], cnt-1);
			return;
		}
		
		for(int i=start; i<s.length(); i++){
			boolean isPalindrome = false;
			String substr = s.substring(start, i+1);
			if(ht.get(substr) != null){
				isPalindrome = ht.get(substr);
			}else{
				isPalindrome = checkPalindrome(substr);
				ht.put(substr, isPalindrome);
			}
			if(isPalindrome){
				al.add(substr);
				dfs(s, i+1, ht, ret, al, cnt+1, min);
				al.remove(al.size()-1);
			}
		}
	}

	public static boolean checkPalindrome(String s){
		if(s.length() == 0){
			return true;
		}
		for(int i=0; i<=s.length()/2; i++){
			if(s.charAt(i) != s.charAt(s.length()-1-i)){
				return false;
			}
		}
		return true;
	}
	
}