Worst case runtime analysis of a string partitioning algorithm

Question

Give all the partitionings of a string s such that every substring of the partition is a palindrome

What is the time complexity of this solution? And, how can I improve my code overall?

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();
            resultLst.add(r);
    }
    for(int i=l;i<s.length();i++){
        if(isPalindrome(s,l,i)){
            if(l==i)
                currLst.add(Character.toString(s.charAt(i)));
            else
                currLst.add(s.substring(l,i+1));
            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;
}

Answer 1

From looking at your code, I'd think it would be \$O(n^2)\$ or \$O(n^3)\$. I got this by:

• backTrack() is called n times
• backTrack() has a for loop, which is executed m-n times
• In that for loop, isPalindrome() is called, which has the complexity of \$O(\frac{r-l}2)\$

Putting it together, I get:

$$O(\frac{n(n+1)(2n+1)}6)$$

I am not sure if I'm right; correct me if I'm wrong.

Since 1, 2, 4, and 6 are not significant, we can remove them, to get:

$$O(n^3)$$

I can't think of a better algorithm, but maybe there is one. I will concentrate on the naming of your variables, and other conventions.

Formatting

All right, time to complain about how bad your formatting is, part by part...

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();
            resultLst.add(r);
    }
    for(int i=l;i<s.length();i++){
        if(isPalindrome(s,l,i)){
            if(l==i)
                currLst.add(Character.toString(s.charAt(i)));
            else
                currLst.add(s.substring(l,i+1));
            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;
}

First of all, extra newline between methods. This allows easier readability.

Now, to the first section:

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); // Line 7
    return resultLst;
}

My suggestions:

Line 7: Space after comma

Well.. that was easy. Next...

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();
            resultLst.add(r);
    }
    for(int i=l;i<s.length();i++){ // Line 7
        if(isPalindrome(s,l,i)){
            if(l==i)
                currLst.add(Character.toString(s.charAt(i)));
            else
                currLst.add(s.substring(l,i+1));
            backTrack(s,i+1);
            currLst.remove(currLst.size()-1);
        }
    }
}

Line 1: Space before brace

Line 2: Space after if
Line 2: Space before and after >, or any other operator, for that matter
Line 2: Usually, though optional, there is a space after // in end-of-line comments

Line 3: It is recommended to use two tabs, or 8 spaces, for a continued line.
Line 3: Again, space before and after all operators.

Line 4-5: Here, it should be 4 spaced.

Line 7: Space after for
Line 7: Space before and after operators, twice
Line 7: Space after semicolons
Line 7: Space before brace

Line 8: Space after if
Line 8: Space before brace
Line 8: Space after commas

Line 9: Space after if
Line 9: Space before and after operators Line 9: ALWAYS put braced for if statements. I explain it here.

Line 11: Again, ALWAYS put braced for if statements, including else.
Line 11: Space after comma
Line 11: Space before and after operators

Line 12: Space before and after operators
Line 12: Space after comma

Line 13: Space before and after operators
Line 13: Space after comma

Line 14: Space before and after operators

Now that was quite a bit. Notice that most of my suggestions appear over and over and over again.

Next...

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;
}

Line 1: Space before brace (hey, I just realised it rhymes!)

Line 2: Space after if
Line 2: Space before and after operators
Line 2: Here, I do see a reason why you made it a one-liner. I would usually not do so, but I wouldn't complain if I saw it.

Line 3: Space after while
Line 3: Space before and after operators
Line 3: Space before brace

Line 4: Space after if
Line 4: Space before and after operators
Line 4: Again, I do see a reason why you made it a one-liner.

Line 5: Separate into two lines. I would never put two statements on one line, no matter how related.

Done! Result after formatting:

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();
        resultLst.add(r);
    }
    for (int i = l; i < s.length(); i++) {
        if (isPalindrome(s, l, i)) {
            if (l == i) {
                currLst.add(Character.toString(s.charAt(i)));
            } else {
                currLst.add(s.substring(l, i + 1));
            }
            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;
}

Naming

Most of your variable names are not exactly good. Names say what the variable is for, and is not just there to identify a from b. I would suggest:

• resultLst -> result
• currLst -> currentList
• resultLst -> result

In partition():

• s -> string or toPartition

In backtrack():

• s -> string or toPartition
• l -> len or length
• r -> list or toAdd

In isPalindrome():

• str -> string
• l -> from
• r -> to

Result:

List<List<String>> result;
ArrayList<String> currentList;

public List<List<String>> partition(String string) {
    result = new ArrayList<List<String>>();
    currentList = new ArrayList<String>();
    backTrack(string, 0);
    return result;
}

public void backTrack(String string, int length) {
    if (currentList.size() > 0 // the initial str could be palindrome
            && length >= string.length()) {
        List<String> list = (ArrayList<String>) currentList.clone();
        result.add(list);
    }
    for (int i = length; i < string.length(); i++) {
        if (isPalindrome(string, length, i)) {
            if (length == i) {
                currentList.add(Character.toString(string.charAt(i)));
            } else {
                currentList.add(s.substring(length, i + 1));
            }
            backTrack(string, i + 1);
            currentList.remove(currentList.size() - 1);
        }
    }
}

public boolean isPalindrome(String string, int from, int to) {
    if (from == to) return true;
    while (from < to) {
        if (string.charAt(from) != string.charAt(to)) return false;
        from++;
        to--;
    }
    return true;
}

Misc

• Declare all lists at List<Type>
• result and currentList should be private