Question9_5.java

import java.util.LinkedList;

/**
 * Write a method to compute all permutations of a string of unique characters.
 *  
 * Time  Complexity: O(n!)
 * Space Complexity: O(n!)
 */

public class Question9_5 {
    public LinkedList<String> permutations(String str) {
        LinkedList<String> permutations = new LinkedList<String>();
        
        if (str != null) {
            permutations.add("");
            char[] characters = str.toCharArray();
            for (int i = 0; i < characters.length; ++i) {
                char letter = characters[i];
                int size = permutations.size();
                for (int j = 0; j < size; ++j) {
                    StringBuffer permutation = new StringBuffer(permutations.get(j));
                    for (int k = 0; k <= permutation.length(); ++k) {
                        permutation.insert(k, letter);
                        permutations.add(permutation.toString());
                        permutation.deleteCharAt(k);
                    }
                }
            }
        }
        
        return permutations;
    }
    
    
    
    public static void main(String[] args) {
        Question9_5 question9_5 = new Question9_5();
        LinkedList<String> permutations = question9_5.permutations("mu");
        for (String permutation : permutations) {
            System.out.println(permutation);
        }
    }
}