# Java: Easy to Understand DP+Backtracking (7ms)

• First compute and store the palindromes start from each position. Time: O(N^2)

Then use this information to decide the possible next step start positions in backtracking.

Time complexity: there is no way to do better than O(2^N) in worst case, since for "aaaaaaaaaaaaa" there will be ~2^N different partitions.
However, since we only need to test each possible palindrome once in this solution, I would say this should be a fast solution.

``````public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res=new ArrayList<>();
if(s==null||s.length()==0) return res;
/*Compute the palindroms start from each position*/
ArrayList<String>[] pals=new ArrayList[s.length()]; //the palindromes start from index i.
for(int i=0; i<pals.length; i++) pals[i]=new ArrayList<String>();
char[] chars=s.toCharArray();
int len=s.length();
for(int i=0; i<len-1; i++){
/*odd length*/
int left=i, right=i;
while(left>=0 && right<len && chars[left]==chars[right]){
left--;
right++;
}
/*even length*/
left=i; right=i+1;
while(left>=0 && right<len && chars[left]==chars[right]){
left--;
right++;
}
}
List<String> partition=new ArrayList<>();
partition(chars, 0, partition, res, pals);
return res;
}

private void partition(char[] chars, int start, List<String> partition, List<List<String>> res, List<String>[] pals){
if(start==chars.length){
return;
}
List<String> set=pals[start];
for(String str: set){