leetcode--19. palindrome-partit

题目：
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
给定字符串s，分区的每个子字符串都是回文。返回s的所有可能的回文分区。

For example, given s ="aab",
Return
[
["aa","b"],
["a","a","b"]
]

思路：
如果要求输出所有可能的解，往往都是要用深度优先搜索。如果是要求找出最优的解，或者解的数量，往往可以使用动态规划。

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<>();
        help(res,new ArrayList<String>(),s);
        return res;
    }
    private void help(ArrayList<ArrayList<String>> res, ArrayList<String> temp, String s) {
        if(s.length() == 0){
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 1; i <= s.length(); i++) {
            String t = s.substring(0, i);
            if(t.equals(new StringBuffer(t).reverse().toString())){ // 判断是否是回文字符串
                temp.add(t);
                help(res,temp,s.substring(i));
                temp.remove(temp.size()-1);
            }
        }
    }
}