Leetcode 131 Palindrome Partitioning

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"]
  ]

Solution 1: DP + DFS: use DP to store if s[i..j] is palindrome or not. This  will guarantee to be O(N^2) complexity.

 public class Solution {  
   public List<List<String>> partition(String s) {  
     int n=s.length();  
     char c[]=s.toCharArray();  
     boolean[][] dp=new boolean[n][n];//store if s[i..j] is palin or not  
     for (int j=0; j<n; j++) {  
       for (int i=j; i>=0; i--) {  
         if (j==i) dp[i][j]=true;  
         else dp[i][j]=c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]);  
       }  
     }  
     List<String> one=new ArrayList<>();  
     List<List<String>> res=new ArrayList<>();  
     dfs(c,0,dp,one,res);  
     return res;  
   }  
   private void dfs(char[] c, int d, boolean[][] dp, List<String> one, List<List<String>> res) {  
     if (d==c.length) res.add(new ArrayList<String>(one));  
     else {  
       for (int j=d; j<c.length; j++) {  
         if (dp[d][j]) {  
           one.add(new String(c,d,j-d+1));  
           dfs(c,j+1,dp,one,res);  
           one.remove(one.size()-1);  
         }  
       }  
     }  
   }  
 }