current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

This generates all possible permutations of the string. I am also unable to understand the time complexity of this problem. Can someone please explain the complexity to me?

import java.util.ArrayList;


public class permutations {

    public ArrayList<String> performPermutations(String s){
        ArrayList<String> arrayList = new ArrayList<String>();
        if (s == null) {
            return null;
        }

        else if (s.length() == 0) {
            arrayList.add("");
            return arrayList;
        }

        else {
            for (int i = 0; i < s.length(); i++) {
                ArrayList<String> remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
                for (int j = 0; j < remaining.size(); j++) {
                    arrayList.add(s.charAt(i) + remaining.get(j));
                }
            }
            return arrayList;
        }
    }


    public static void main(String[] args) {
        permutations p = new permutations();
        ArrayList<String> arr = p.performPermutations("abcde");
            for(int i = 0; i<arr.size();i++) {
                System.out.println(arr.get(i));
            }
        }
    }
}
share|improve this question
4  
We can review your code (if it all works), but not explain the complexity, as we do not assist in explaining code given in the question. –  Jamal♦ Sep 18 at 4:10
1  
Welcome to Code Review, Add an expected input/output along with some more explanation of exactly what your code does. See stackoverflow.com/questions/487258/… –  JaDogg Sep 18 at 7:34

1 Answer 1

up vote 0 down vote accepted

There are quite a few ways this code can be improved:

  • All class names should start with a capital, and be in CamelCase. Specifically, the class permutations should be Permutations. The way it doesn't look like a variable, as in here:

    permutations p = new permutations();

performPermutations method

  • Why does it declare a return type of ArrayList<String>? Is there anything special about the implementation of the list? It should just be List<String>.

  • You have an unnecessary if-else structure, since each if statement returns a value. You can remove all of the elses.

  • In the first if statement, you return null. This is a bad idea in many cases. An empty list would be more favorable, just in case any calling code wants to operate on it immediately afterwards. (Notice that your main method would fail with a NullPointerException if the passed in list was empty).

  • You can combine the first and second if statements into one. This would be your "base" case:

    if (s == null || s.isEmpty() { return arrayList; }

    Never compare a list length to 0, use isEmpty() instead. Also, s is a poor name for a method parameter. Try to be creative and descriptive. Finally, there's no need to add an empty string if the list is empty.

  • There's a lot of existing posts on string permutations you may find interesting. Seeing a recursive call embedded in two for loops is probably unnecessarily complex.

How this method could look (but can still be improved):

public List<String> performPermutations(String s){

    List<String> result = new ArrayList<String>();

    if (s == null || s.isEmpty()) {
        return result;
    }

    for (int i = 0; i < s.length(); i++) {
        List<String> remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
        for (int j = 0; j < remaining.size(); j++) {
            result.add(s.charAt(i) + remaining.get(j));
        }
    }

    return result;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.