[Leetcode] Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

做完longest palindromic substring之后
http://ftalm.blogspot.com/2015/10/leetcode-longest-palindromic-substring.html
这题 明朗了很多 就是和longest palindromic substring（建所有substring 是否palindrom的table+DFS)

public class Solution {
    List> result = new ArrayList>();
    boolean check[][];
    List temp = new ArrayList();
    public List> partition(String s) {
        check = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++){
            check[i][i] = true;
            for (int j = 0; j < i; j++){
                check[j][i] = s.charAt(j) == s.charAt(i) && (i-j==1 || check[j+1][i-1]);
            }
        }
        findSol(0, temp, s);
        return result;
    }
    
    private void findSol(int start, List list, String str){
        if (start == str.length()){
            result.add(new ArrayList(list));
            return;
        }
        for (int i = start; i < str.length(); i++){
            if (check[start][i]){
                list.add(str.substring(start, i+1));
                findSol(i+1, list, str);
                list.remove(list.size()-1);
            }
        }
    }
}