Palindrome Partitioning (LeetCode Backtracking)

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

Idea: Brute force depth-first search. For the input string, split it to two halves at any "valid" positions, where valid means the prefix is a valid palindrome. Then recursively partition the suffix part.

Time: O(n^n) Space: O(n)

Code:

 public class Solution {  
   public List<List<String>> partition(String s) {  
     List<List<String>> result=new ArrayList<List<String>>();  
     List<String> path=new ArrayList<String>();  
     dfs(result,path,0,s);  
     return result;  
   }  
   public boolean isValid(String s)  
   {  
     for(int i=0;i<s.length()/2;i++)  
     {  
       if(s.charAt(i)!=s.charAt(s.length()-1-i))  
         return false;  
     }  
     return true;  
   }  
   public void dfs(List<List<String>> result, List<String> path, int cur,String s)  
   {  
     if(cur==s.length())  
     {  
       result.add(new ArrayList<String>(path));  
       return;  
     }  
     for(int i=cur+1;i<=s.length();i++)  
     {  
       String prefix=s.substring(cur,i);  
       if(isValid(prefix)==false)  
         continue;  
       String next=s.substring(i,s.length());  
       path.add(prefix);  
       dfs(result,path,i,s);  
       path.remove(path.size()-1);  
     }  
   }  
 }