Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]

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

    private void dfs(String s, int start, List<String> cur, List<List<String>> res) {
        if(start == s.length()) {
            res.add(new ArrayList<String>(cur));
            return;
        }
        for(int i = start; i < s.length(); i++) {
            if(isPal(s, start, i)) {
                String palSec = s.substring(start, i + 1);
                cur.add(palSec);
                dfs(s, i + 1, cur, res);
                cur.remove(cur.size() - 1);
            }
        }
    }

    private boolean isPal(String s, int start, int end) {
        while(start < end) {
            if(s.charAt(start++) != s.charAt(end--)) {
                return false;
            } 
        }
        return true;
    }
}

method 2.与上面方法类似，省去指针，每次传string都是传去掉前面palindromic部分
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        dfs(s, cur, res);
        return res;
    }

    private void dfs(String s, List<String> cur, List<List<String>> res) {
        if(s.length() == 0) {
            res.add(new ArrayList<String>(cur));
            return;
        }
        for(int i = 0; i < s.length(); i++) {
            String sub = s.substring(0, i + 1);
            if(isPal(sub)) {
                cur.add(sub);
                dfs(s.substring(i + 1, s.length()), cur, res);
                cur.remove(cur.size() - 1);
            }
        }
    }

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