Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res=new ArrayList<>();
boolean[][] isPal=computePal(s);
helper(isPal,s,0,res,new ArrayList<>());
return res;
}
public void helper(boolean[][] isPal,String s,int pos,List<List<String>> res,List<String> list){
if(pos==s.length()){
res.add(new ArrayList<>(list));
return;
}
for(int i=pos;i<s.length();i++){
if(isPal[pos][i]){
list.add(s.substring(pos,i+1));
helper(isPal,s,i+1,res,list);
list.remove(list.size()-1);
}
}
}
public boolean[][] computePal(String s){
boolean[][] res=new boolean[s.length()][s.length()];
for(int i=0;i<s.length();i++){
for(int j=0;j<=i;j++){
if(s.charAt(j)==s.charAt(i) && (j+1>i-1 || res[j+1][i-1])){
res[j][i]=true;
}
}
}
return res;
}
}