Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/
给定一个字符串S，求出这个字符串的子集，满足每一个子字符串都是回文字符串

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

DFS大法

dfs的定义：从第start个元素开始，到字符串结尾的所有回文子集字符串的集合

input: "aab"
dfs("aab",0,out,res);  out = ["a"];
     dfs("aab",1,out,res);out = ["a","a"];
         dfs("aab",2,out,res); out = ["a","a","b"];
             dfs("aab",3,out,res) out = ["a","a","b"]; res = [["a","a","b"]];
        dfs("aab",2,out,res);out=["a","a"]
    dfs("aab",1,out,res);out=["a"]
dfs("aab",0,out,res); out = ["aa"];
   dfs("aab",1,out,res);out = ["aa","b"];
  ...
  ...

/**
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        List<String> item = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();

        if (s == null || s.length() == 0) {
            return res;
        }

        partitionHelper(s, 0, item, res);
        return res;
    }


    //从第start个元素开始，到字符串结束，能组成的所有回文字符串子集
    public void partitionHelper(String s, int start, List<String> out, List<List<String>> res) {

        //当start等于s的长度，实际上已经超出了s的index范围（s的index范围是0~s.length-1）
        //把out作为一个结果集放入res中
        if (start == s.length()) {
            res.add(new ArrayList<String>(out));
            return;
        }


        for (int i = start; i < s.length(); i++) {
            //从第start个元素开始遍历，如果第start到第i+1之间的子集为回文子串
            //则继续计算i+1后面余下的子串的回文问题
            String str = s.substring(start, i + 1);
            if (isPalindrome2(str)) {
                out.add(str);
                partitionHelper(s, i + 1, out, res);
                out.remove(out.size() - 1);
            }
        }
    }

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