CTCI 9.5

Write a method to compute all permutations of a string.

CTCI 9.5-1.java

/*
 * get all distinct permutations of the string
 * "abc" => [abc, acb, bac, bca, cba, cab]
 * "abcc" = > [abcc, acbc, accb, bacc, bcac, bcca, cbac, cbca, cabc, cacb, ccab, ccba]
 */
public static ArrayList<String> permutations(String input){
    if(input == null) return null;
    if(input == "") return new ArrayList<String>(Arrays.asList(""));
    ArrayList<String> output = new ArrayList<>();
    permutations(input.toCharArray(), 0, output);
    return output;
}

public static void permutations(char[] input, int index, ArrayList<String> output){
    if(index == input.length) output.add(String.valueOf(input));
    for(int i = index; i < input.length; i++){
        boolean hasBefore = false;
        for(int j = i - 1; j >= index; j--){
            if(input[i] == input[j]){
                hasBefore = true;
                break;
            }
        }
        if(hasBefore) continue;
        swap(input, index, i);
        permutations(input, index + 1, output);
        swap(input, index, i);
    }
}

public static void swap(char[] input, int indexA, int indexB){
    char temp = input[indexA];
    input[indexA] = input[indexB];
    input[indexB] = temp;
}

CTCI 9.5-2.java

/*
 * get all distinct permutations of the subsets of the string
 * "abc" = > [, a, ab, abc, ac, acb, b, ba, bac, bc, bca, c, ca, cab, cb, cba]
 * "abb" = > [, a, ab, abb, b, ba, bab, bb, bba]
 */
public static ArrayList<String> permutationsOfSubsets(String input){
    ArrayList<String> al = permutationsOfSubsetsHelp(input);
    TreeSet<String> tree = new TreeSet<>();
    tree.addAll(al);
    return new ArrayList<String>(tree);
}

public static ArrayList<String> permutationsOfSubsetsHelp(String input){
    if(input.equals("")) return new ArrayList<String>(Arrays.asList(""));
    String lastChars = input.substring(1);
    ArrayList<String> lastList = permutationsOfSubsetsHelp(lastChars);
    char thisChar = input.charAt(0);
    ArrayList<String> output = new ArrayList<>(lastList);
    for(String last : lastList) for(int i = 0; i <= last.length(); i++) output.add(addCharAtIndex(last, thisChar, i));
    return output;
}

public static String addCharAtIndex(String last, char thisChar, int i){
    String before = last.substring(0, i);
    String after = last.substring(i);
    return before + String.valueOf(thisChar) + after;
}