leetcode 字符串分割对称

 1 public class Solution {
 2     public List<List<String>> partition(String s) {
 3         int len=s.length();
 4            boolean dp[][]=new boolean[len][len];
 5            get(dp,s);
 6            ArrayList<ArrayList<String>> res=new ArrayList<ArrayList<String>>();
 7            ArrayList<String> temp=new ArrayList<String>();
 8            dfs(res,temp,0,dp,s);
 9            return (List)res;
10            
11         
12     }
13     public void get(boolean dp[][],String s)
14     {
15         char c[]=s.toCharArray();
16         int len=s.length();
17       //single character is duichen
18       for(int i=0;i<len-1;i++)
19       {
20           dp[i][i]=true;
21           if(c[i]==c[i+1]) dp[i][i+1]=true;
22           
23       }
24       dp[len-1][len-1]=true;
25         
26         for(int l=2;l<len;l++)
27         {
28             for(int k=0;k<len-l;k++)
29             {
30                 dp[k][k+l]=dp[k+1][k+l-1]&&(c[k]==c[k+l]);
31             }
32     
33         }
34         
35         
36         
37     }
38 public void dfs(ArrayList<ArrayList<String>> res,ArrayList<String> temp,int l,boolean dp[][],String s)
39     {
40         if(l==dp.length)
41         {
42            res.add(new ArrayList(temp));   
43         }
44         else
45         {
46             for(int j=0;j<dp.length;j++)
47             {
48                 if(dp[l][j])
49                 {
50                     ArrayList<String> t=new ArrayList<String>(temp);
51                     t.add(s.substring(l,j+1));
52                     dfs(res,t,j+1,dp,s);
53                     
54                 }
55                     
56                 
57             }
58                 
59              }
60     }
61     
62     
63     
64     
65 }