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);

                 }

             }

              }

     }

 }