文字列区切り


タイトル:
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"]
  ]

コード:
public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<String>> list = null;
        
        int len = s.length();
        
        boolean[][] isPalin = new boolean[len][len];
        
        for(int i=0;i<len;i++){
            for(int j=0;j<=i;j++){
                if(s.charAt(i) == s.charAt(j) && (i-j < 2 || isPalin[j+1][i-1])){
                    isPalin[j][i] = true;
                }
            }
        }
        
        list = result(s,isPalin,0,len);
        
        for(ArrayList<String> l : list){
            Collections.reverse(l);
        }
        
        return list;
    }
    
    public ArrayList<ArrayList<String>> result(String s,boolean[][] isPalin,int start,int max){
        if(start >= max){
            ArrayList<String> l = new ArrayList<String>();
            ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
            list.add(l);
            return list;
        }
        
        ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>(); 
        
        for(int i=start;i<max;i++){
            if(isPalin[start][i]){
                ArrayList<ArrayList<String>> list = result(s,isPalin,i+1,max);
                String temp = s.substring(start,i+1);
                for(ArrayList<String> l : list)
                    l.add(temp);
                all.addAll(list);
            }
        }
        
        return all;
    }
}