public class Solution {
public List<List<String>> partition(String s) {
int len=s.length();
boolean dp[][]=new boolean[len][len];
get(dp,s);
ArrayList<ArrayList<String>> res=new ArrayList<ArrayList<String>>();
ArrayList<String> temp=new ArrayList<String>();
dfs(res,temp,0,dp,s);
return (List)res;
}
public void get(boolean dp[][],String s)
{
char c[]=s.toCharArray();
int len=s.length();
//single character is duichen
for(int i=0;i<len-1;i++)
{
dp[i][i]=true;
if(c[i]==c[i+1]) dp[i][i+1]=true;
}
dp[len-1][len-1]=true;
for(int l=2;l<len;l++)
{
for(int k=0;k<len-l;k++)
{
dp[k][k+l]=dp[k+1][k+l-1]&&(c[k]==c[k+l]);
}
}
}
public void dfs(ArrayList<ArrayList<String>> res,ArrayList<String> temp,int l,boolean dp[][],String s)
{
if(l==dp.length)
{
res.add(new ArrayList(temp));
}
else
{
for(int j=0;j<dp.length;j++)
{
if(dp[l][j])
{
ArrayList<String> t=new ArrayList<String>(temp);
t.add(s.substring(l,j+1));
dfs(res,t,j+1,dp,s);
}
}
}
}
}
