Q: Generating all permutations of a given string

D: What is an elegant way to find all the permutations of a string. E.g. ba, would be ba and ab, but what about abcdefgh? Is there any example Java implementation?

Test Case #6


File ID: #4240323-0-cc


public void permutation(String s) {
    permutation("", s);
}
private void permutation(String prefix, String s) {
    int len = s.length();
    System.out.println(prefix);
    for (int i = 0; i < len; i + +) {
        permutation(prefix + s.substring(i, i + 1), s.substring(0, i ) + s.substring(i +1, len));
    }
}

  1. That's not rocket science, I came up with pretty much the same answer. Minor tweak: instead of recursing until `n==0`, you can stop a level earlier at `n==1` and print out `prefix + str`.
  2. I think str.substring(i+1, n) can be replaced by str.substring(i+1). Using str.substring(i) will cause java.lang.StackOverflowError.
  3. "what is the time and space complexity of this?" without some sort of partial answer caching any algorithm that outputs permutation is o(n!) because the result set to the permutation question is factorial to the input.

Comments Quality
Accurate?:
Precise?:
Concise?:
Useful?: