[LeetCode] Palindrome Partitioning I&II

    對于Palindrome Partitioning I ，題目對于時間複雜度要求不是很高（因為要求所有情況），是以直接搜尋，或者先做dp擷取之情兩點間字元串是否回文，之後對這一步得到的二維數組進行dfs或者dp都是可以的

方法一：

public class Solution {
	public List<List<String>> partition(String s) {
		if(s.length()==0) return re; 
		dp=getDp(s);
		backtrace(0,s);
		return re;
	}
	List<List<String>> re=new ArrayList<List<String>>();
	List<String> trace=new ArrayList<String>();
	boolean[][] dp;
	public void backtrace(int k,String s){
		if(k==s.length()){
			re.add(new ArrayList<String>(trace));
			return;
		}
		for(int i=k+1;i<=s.length();i++){
			String str=s.substring(k,i);
			if(dp[k][i-1]){
				trace.add(str);
				backtrace(i,s);
				trace.remove(trace.size()-1);
			}
		}
	}
    public boolean[][] getDp(String s){
	   char[] ss=s.toCharArray();
	   boolean dp[][]=new boolean[ss.length][ss.length];
	   for(int i=0;i<ss.length;i++){
		   dp[i][i]=true;
	   }
	   for(int len=1;len<ss.length;len++){
		   for(int i=0;i<ss.length-len;i++){
			   int j=i+len;
			   if(i+1>j-1)
				   dp[i][j]=ss[i]==ss[j];
			   else
				   dp[i][j]=dp[i+1][j-1]&&ss[i]==ss[j];
		   }
	   }
	   return dp;
   }
    public static void main(String[] args) {
		Solution s=new Solution();
		System.out.println(s.partition("aab"));
	}
}
           

方法二(dp)：  

(懶得再寫一遍，是以copy他人的）

public class Solution3 {
	//dp  效率更高
    public static List<List<String>> partition(String s) {
		int len = s.length();
		List<List<String>>[] result = new List[len + 1];
		result[0] = new ArrayList<List<String>>();
		result[0].add(new ArrayList<String>());

		boolean[][] pair = new boolean[len][len];
		for (int i = 0; i < s.length(); i++) {
			result[i + 1] = new ArrayList<List<String>>();
			for (int left = 0; left <= i; left++) {
				if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
					pair[left][i] = true;
					String str = s.substring(left, i + 1);
					for (List<String> r : result[left]) {
						List<String> ri = new ArrayList<String>(r);
						ri.add(str);
						result[i + 1].add(ri);
					}
				}
			}
		}
		return result[len];
	}
}
           

對于Palindrome Partitioning II，技巧相似，先dp，再對所得二維數組dp或者dfs：

代碼：

public class Solution {
	//分析：先用dp做預處理  之後的所有操作相當于做一個從s.length()-1向前的搜尋
	//注意：為了讓決策樹更簡介 是以做預處理都将從前往後的搜尋轉換為從後向前
	//對于一個從後向前的搜尋  最小子問題是從前向後的  是以可以通過對map進行前往後的dp或者從後向前的dfs實作
	  public int minCut(String s) {
		  if(s.length()==0) return 0;
	        boolean[][] map=getDp(s);
	        int[] dp=new int[s.length()+1];
	        for(int i=0;i<s.length();i++){//這段dp代碼是可以轉換為對map的dfs的
	        	dp[i+1]=i+1;
	        	for(int j=0;j<=i;j++){
	        		if(map[j][i]) dp[i+1]=Math.min(dp[j+1-1]+1,dp[i+1]);
	        	}
	        }
	        return dp[dp.length-1]-1;
 	  }
	  public boolean[][] getDp(String s){
		  boolean[][] dp=new boolean[s.length()][s.length()];
		  for(int len=0;len<s.length();len++){ //這裡下标不要弄錯
			  for(int i=0;i<s.length()-len;i++){
				  int j=i+len;
				  if(i==j) dp[i][j]=true;
				  else if(i==j-1){
					 dp[i][j]=s.charAt(i)==s.charAt(j);
				  }else{
					  dp[i][j]=dp[i+1][j-1]&&s.charAt(i)==s.charAt(j);
				  }
			  }
		  }
		  return dp;
	  }
}