[leetcode]Palindrome Partitioning

新博文地址：[leetcode]Palindrome Partitioning

新代码要简洁一点。。。。

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
["aa","b"],
["a","a","b"]
]

 将字符串分割，每一小段都是回文段，返回所有的分割情况。DFS不解释啊。

算法思想：

首先检查s的前i个字符的子串是不是回文串，如是就递归检查从i+1往后的字串，否则就返回，检查前i+1个字符形成的子串。

对回溯算法用的还不是很熟悉，感觉代码总是略长，但是好在更容易理解。

ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
	public ArrayList<ArrayList<String>> partition(String s) {
		if(s == null || s.length() == 0){
			return result;
		}
		for(int i = 0 ; i < s.length(); i++){
			ArrayList<String> subList = new ArrayList<String>();
			String subStr = s.substring(0, i + 1);//得到前i个字符的子串
			if(isPalindrome(subStr)){//如果是回文的，则递归
				subList.add(subStr);
				dfs(s.substring(i + 1), subList);
				subList.remove(subList.size() - 1);//回溯
			}
		}
		return result;
	} 
	
	private void dfs(String s,ArrayList<String> list){
		if(s.length() == 0){
			ArrayList<String> cpy = new ArrayList<String>(list);
			result.add(cpy);
			return;
		}
		
		for(int i = 0; i < s.length(); i++){
			String subStr = s.substring(0, i + 1);
			if(isPalindrome(subStr)){
				list.add(subStr);
				dfs(s.substring(i + 1),list);
				list.remove(list.size() - 1);
			}
			
		}
	}
	
	private boolean isPalindrome(String s){
		for(int i = 0; i < s.length()>>1; i++){
			if(s.charAt(i)!= s.charAt(s.length() - 1 - i)){
				return false;
			}
		}
		return true;
	}