# Concise Java Solution

• ``````public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res=new ArrayList<List<String>>();
if(s.length()==0)return res;
recur(res,new ArrayList<String>(),s);
return res;
}

public void recur(List<List<String>> res,List<String> temp, String s){
if(s.length()==0){
return;
}
for(int i=0;i<s.length();i++){
if(isPalin(s.substring(0,i+1))){
recur(res,temp,s.substring(i+1));
temp.remove(temp.size()-1);
}
}
}

public boolean isPalin(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;
}
}``````

• Similar idea.

In order to check whether a string is palindrome, simply compare to reversed itself.

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

public void partition(List<List<String>> res, List<String> list, String s) {
if(isPali(s)) {
List<String> l = new ArrayList<String>(list);
}

for(int i = 1; i < s.length(); i++) {
String s1 = s.substring(0, i), s2 = s.substring(i, s.length());
if(isPali(s1)) {
List<String> ll = new ArrayList<String>(list);
partition(res, ll, s2);
}
}
}

public boolean isPali(String s) {
return s.equals(new StringBuilder(s).reverse().toString());
}
}``````

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

• @SpicyDog More concise, but using sb to check for palindrome is slower.

• said in Concise Java Solution:

``````    return res;
``````

@jie17 can you please let me know the time complexity of the code

• @nikhilay I think the time complexity is O(n! * n * n) . Here n presents the length of the given string. n! is for the n-branch tree with n-level depth. The rest one n is for the palindrome check and another n is for the substring method.

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