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，时间分析，一个有n-1的地方可以断开，所以有断和不断两种情况，所有情况就是2^n。 

public class Solution {
    //Time: O(2^n)
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> tmp = new ArrayList<String>();
        help(res, tmp, s, 0);
        return res;
    }
    
    private void help(ArrayList<ArrayList<String>> res, ArrayList<String> tmp, 
                      String s, int index) {
        if (index == s.length()) {
            res.add(new ArrayList<String>(tmp));
            return;
        }
        
        for (int i = index + 1; i <= s.length(); i++) {
            String cur = s.substring(index, i);
            if (valid(cur)) {
                tmp.add(cur);
                help(res, tmp, s, i);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    
    private boolean valid(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}