# Java: Backtracking solution.

• if the input is "aab", check if [0,0] "a" is palindrome. then check [0,1] "aa", then [0,2] "aab".
While checking [0,0], the rest of string is "ab", use ab as input to make a recursive call.

in this example, in the loop of i=l+1, a recursive call will be made with input = "ab".
Every time a recursive call is made, the position of l move right.

How to define a correct answer?
Think about DFS, if the current string to be checked (Palindrome) contains the last position, in this case "c", this path is a correct answer, otherwise, it's a false answer.

line 13: is the boundary to check if the current string contains the last element.
l>=s.length()

``````public class Solution {
List<List<String>> resultLst;
ArrayList<String> currLst;
public List<List<String>> partition(String s) {
resultLst = new ArrayList<List<String>>();
currLst = new ArrayList<String>();
backTrack(s,0);
return resultLst;
}
public void backTrack(String s, int l){
if(currLst.size()>0 //the initial str could be palindrome
&& l>=s.length()){
List<String> r = (ArrayList<String>) currLst.clone();
}
for(int i=l;i<s.length();i++){
if(isPalindrome(s,l,i)){
if(l==i)
else
backTrack(s,i+1);
currLst.remove(currLst.size()-1);
}
}
}
public boolean isPalindrome(String str, int l, int r){
if(l==r) return true;
while(l<r){
if(str.charAt(l)!=str.charAt(r)) return false;
l++;r--;
}
return true;
}
}
``````

• Great illustration and explanation!
I had the same AC solution in c++, 13ms.

I used a "tmp string vector" throughout the recursion call path, and push it to the "result vector" only if it successfully reach the end of the original string (all partitions are Palindromes).

``````class Solution {
public:
vector< vector<string> > partition(string s) {
vector< vector<string> > result;
vector< string > tmp;
recurPartition(s, 0, tmp, result);
return result;
}
void recurPartition(string &s, int start, vector<string> &tmp, vector< vector<string> > &result){
if(start==s.size()){
result.push_back(tmp);
}
for(int i=start+1; i<=s.size();i++){
if(isPalindrome(s, start, i)){
tmp.push_back(s.substr(start, i-start));
recurPartition(s, i, tmp, result);
tmp.pop_back();
}
}
}
bool isPalindrome(string &s, int begin, int end){
int left=begin;
int right=end-1;
while(left<right){
if(s[left++]!=s[right--])
return false;
}
return true;
}
};
``````

• Can anyone provide a time complexity analysis for this solution?

• Thanks for your sharing. This is a little bit cleaner version of your thought.

``````public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<List<String>>();
List<String> list = new ArrayList<String>();
dfs(s,0,list,res);
return res;
}

public void dfs(String s, int pos, List<String> list, List<List<String>> res){
else{
for(int i=pos;i<s.length();i++){
if(isPal(s,pos,i)){
dfs(s,i+1,list,res);
list.remove(list.size()-1);
}
}
}
}

public boolean isPal(String s, int low, int high){
while(low<high) if(s.charAt(low++)!=s.charAt(high--)) return false;
return true;
}

}``````

• What's the time complexity of this method? In the dfs(), there is a for loop, which is O(n); isPal() is another O(n); substring() is another O(n); and dfs() is another O(n). So can I say that it's O(n^4) in the worst case?

• Roughly,
T(n)=T(n-1)+T(n-2)+..+T(1)

T(n+1)=T(n)+T(n-1)+..+T(1)

T(n+1)=2T(n)

T(n)=2^n

• if(pos==s.length() && list.size()>0) , the condition list.size() > 0 is not really necessary.

• Fix that, thank you.

• Time complexity is O(n*(2^n)). The function isPalindrome is O(n)

• said in Java: Backtracking solution.:

backTrack

This is certainly a backtracking solution, but I think we may end up processing the same index multiple times.
For example, given "aab", we could reach index l=2 via:

1. a + a -> b
2. aa -> b
In that sense, we should use memoization to avoid duplicated calculation. So shouldn't the best solution be DP instead of backtracking?

• Why should we remove the last one E of List?

``````currLst.remove(currLst.size()-1);
``````

or

``list.remove(list.size()-1);``

• Just wondering.. in the second graph, should the node contains "aab" be marked as pink cuz "aab" is not a palindrom?

• Hi,guys, First of all,great method, voted. Secondly, I am a rookie in programming , when i saw the method in word break II ,i learned the method of memorized search , so i try to use it in this problem, but the efficiency is quite bad,just beat 14%, I wander why it's like this,thanks a lot. ^^
my codes are as below.

``````    Map<String,List<List< String> > > map= new HashMap<>();

public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<List<String>>();
if(s==null || s.equals("")) {
return res;
}
res =  dfs(s,map);
for(List<String> l: res){
l.remove(l.size()-1);
}
return res;

}

public List<List<String>> dfs(String s, Map<String,List< List<String>>> map){
if(map.containsKey(s) ){
return map.get(s);
}
List<List<String> > res = new ArrayList<List<String>>();
if(s.equals( "") ){
map.put(s,res);
return res;
}
for(int i =1;i<=s.length();i++){
String pres= s.substring(0,i);
if(isPalin(pres ) ){
List<List<String>> prelist= dfs(s.substring(i),map );
for(List<String> ll : prelist){
}
}
}
map.put(s,res);
return res;
}

public boolean isPalin(String s){
int i=0,j=s.length()-1;
while(i<=j){
if(s.charAt(i++)!=s.charAt(j--) )
return false;
}
return true;
}
``````

• @LathamZ that is how "backtracking" works.

• @ming_tsai Thanks, I got it.

• Time complexity: O(n*(2^n))
For a string with length n, there will be (n - 1) intervals between chars.
For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string.
For every partition way, we need to check if it is palindrome, which is O(n).
So the time complexity is O(n*(2^n))
Correct me if I'm wrong.

• @GaoLiaoLiao The total number of recursions is 2^(n-1), this is following the same logic to subsets. But in each recursion, we have a for loop and the function to determine palindrome inside the loop. So I am guessing the time complexity is like O((n^2)(2^n)).

• This post is deleted!

• @charlie-yupeng Thanks for your method,I really appreciate your intelligence.

• Why ["a", "ab"] not a valid answer?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.