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

總結(jié)見(jiàn)：http://www.reibang.com/p/883fdda93a66

Solution1：Backtracking(DFS)，

思路：回溯法灼伤，從start到n 取i開(kāi)始測(cè)試substr(start, i)是否為回文韵洋，如果是的話嗜湃，再DFS繼續(xù)測(cè)試substr(start=i, next_i)是否回文作箍，遞歸繼續(xù)片橡。到底后或者發(fā)現(xiàn)不是患雇，step back by removing回溯到上一步, i=i+1跃脊，繼續(xù)測(cè)試substr(start, i)。
回溯順序：
輸入abcdef
測(cè)試a, b, c, d, e
測(cè)試ab, 如是繼續(xù)測(cè)c, cd, cde..
測(cè)試abc,如是繼續(xù)測(cè)c, cd, cde...

Time Complexity: O(2^N *N)： 2^N組合次數(shù)(每個(gè)字符可以cut or not)苛吱，and isPalindrome function is O(n)
Space Complexity(不算result的話): O(2n) : n是遞歸緩存的cur_result + n是緩存了n層的普通變量O(1) ? (Not Sure)

Solution1.2：Backtracking(DFS) Round1

Solution1 Code：

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

    public void backtrack(String s, int start, List<String> cur_res, List<List<String>> result) {
        if(start == s.length()) {
            result.add(new ArrayList<>(cur_res));
        }
        
        for(int i = start; i < s.length(); i++) {
            if(!isPalindrome(s, start, i)) {
                continue;
            }
            cur_res.add(s.substring(start, i + 1));
            backtrack(s, i + 1, cur_res, result);
            cur_res.remove(cur_res.size() - 1);
        }
    }

    public boolean isPalindrome(String s, int low, int high){
        while(low < high)
            if(s.charAt(low++) != s.charAt(high--)) return false;
        return true;
    }  
}

Solution1.2 Round1 Code：

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s == null || s.length() == 0) {
            return result;
        }
        List<String> cur_res = new ArrayList<>();
        
        backtrack(s, 0, cur_res, result);
        return result;
    }
    
    private void backtrack(String s, int start, List<String> cur_res, List<List<String>> result) {
        if(start == s.length()) {
            result.add(new ArrayList<String>(cur_res));
            return;
        }
        
        for(int len = 1; len <= s.length() - start; len++) {
            String candidate_str = s.substring(start, start + len);
            if(ifPalindrome(candidate_str)) {
                cur_res.add(candidate_str);
                backtrack(s, start + len, cur_res, result);
                cur_res.remove(cur_res.size() - 1);
            }
        }
    }
    
        
    private boolean ifPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while(left < right) {
            if(str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}