4
\$\begingroup\$

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));
            }
        }
    }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – Jamal Sep 18 '14 at 4:10
  • 1
    \$\begingroup\$ 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/… \$\endgroup\$ – bhathiya-perera Sep 18 '14 at 7:34
3
\$\begingroup\$

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(final String s){

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

    if (s == null) {
        return result;
    }

    for (int i = 0; i < s.length(); i++) {
        final 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;
}
\$\endgroup\$
  • \$\begingroup\$ I believe there's a bug at the if (s == null || s.isEmpty()). By removing the result.add(""), you're returning an empty list up to the parent recursive steps, which will ultimately cause an empty list to be returned overall. \$\endgroup\$ – Rahin May 31 '15 at 3:05
  • \$\begingroup\$ Hmm maybe the page isn't refreshing correctly, but I don't think making the string and the list "final" and removing the isEmpty condition would fix the issue \$\endgroup\$ – Rahin May 31 '15 at 3:25
  • \$\begingroup\$ Please feel free to edit or post a new answer which I'll upvote. It's too late for me to reexamine this answer. \$\endgroup\$ – lealand May 31 '15 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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