leetcode JAVA Palindrome Partitioning 3.45 难度系数3

Question：

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"]
  ]

public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
		ArrayList<ArrayList<String>> results = new ArrayList<>();
		ArrayList<String> result = new ArrayList<>();
		dfs(s,0,result,results);
		return results;
	}

	private void dfs(String s, int step, ArrayList<String> result,
			ArrayList<ArrayList<String>> results) {
		if(step==s.length()){
			results.add(new ArrayList<String>(result));
		}
		for(int i=step;i<s.length();i++){
			String cur = s.substring(step, i+1);
			if(isPalindrome(cur)){
				result.add(cur);
				dfs(s, i+1, result, results);
				result.remove(result.size()-1);
			}
		}
	}

	private boolean isPalindrome(String cur) {
		int start = 0;
		int end = cur.length()-1;
		while(start<end){
			if(cur.charAt(start)!=cur.charAt(end)){
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
}

leetcode JAVA Palindrome Partitioning 3.45 难度系数3

原文：http://blog.csdn.net/yiding_he/article/details/19058421