131. Palindrome Partitioning Leetcode Java

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:

First of all, build a dictionary to get all palindrome substring from i to j. 

Then recursively get all valid palindrome partitions.

The recursion steps:

Base case/terminating case:

When start>=s.length() output this valid partition.

Try s.substring(start,i) if it is a valid palindrome then recursively to find next valid palindrome substring starting at index i+1. 

Back track and then try s.substring(start, i+1)...

  public List<List<String>> partition(String s) {  
     List<List<String>> res=new ArrayList<List<String>>();  
     if(s==null || s.length()==0) return res;  
     boolean[][] dict=getDict(s);  
     helper(dict,s,0,new ArrayList<String>(), res);  
     return res;  
   }  
   public void helper(boolean[][] dict, String s,int start, List<String> items, List<List<String>> res){  
     if(start>=s.length()){  
      List<String> temp=new ArrayList<String>(items);  
      res.add(temp);  
      return;  
     }  
     for(int i=start; i<s.length();i++){  
       if(dict[start][i]){  
         items.add(s.substring(start,i+1));  
         helper(dict,s,i+1,items,res);  
         items.remove(items.size()-1);  
       }  
     }  
   }  
   public boolean[][] getDict(String s){  
     boolean[][] dict=new boolean[s.length()][s.length()];  
     for(int i=s.length()-1;i>=0;i--){  
       for(int j=i;j<s.length();j++){  
         dict[i][j]= (j-i<=1 || dict[i+1][j-1])&& s.charAt(i)==s.charAt(j);  
       }  
     }  
     return dict;  
   }