27字符串排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路分析

递归算法，可以理解为第i位上的字母和自己及其后面的位置上字母进行交换

递归前的swap用来交换字符数组，再递归，即沿着上图一条线走下去。
递归后的swap用使得字符数组的顺序回到进入递归前的状态，这样才不会影响外部的遍历顺序。因为在第一次交换后进入递归运算的时候，字符数组的顺序改变了，例如“abc”， i = 0时对应‘a’，j = 1时对应 ‘b’，进行一次交换，此时的字符数组的顺序为 “bac”，从递归返回时，顺序依然是“bac”，则进行第二次交换使得 “bac” -> “abc”，这样在后续才可以进行’a’与’c’的交换，否则会落下某一种情况。

代码实现

private static ArrayList<String> arrayList = new ArrayList<>();

public static ArrayList<String> Permutation(String str) {
    if (str == null || str.length() == 0 || str.length() >= 10) {
        return arrayList;
    }
    char[] chars = str.toCharArray();
    process(chars, 0);
    //用Collections.sort能排列list
    //可以自己实现一个比较器实现字典序
    Collections.sort(arrayList);
    //arrayList.sort(new MyComparator());
    return arrayList;
}
/**
 * 第i位上的字母向后交换
 * @param chars
 * @param i
 */
public static void process(char[] chars, int i) {
    if (i == chars.length) {
        if (!arrayList.contains(String.valueOf(chars))) {
            arrayList.add(String.valueOf(chars));
        }
    }
    for (int j = i; j < chars.length; j++) {
        swap(chars, i, j);
        process(chars, i + 1);
        swap(chars, i, j);
    }
}

public static void swap(char[] chars, int i, int j) {
    char tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
}

public static class MyComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        char[] chars1 = o1.toCharArray();
        char[] chars2 = o2.toCharArray();
        for (int i = 0; i < chars1.length; i++) {
            if (chars1[i] == chars2[i]) {
                continue;
            } else {
                return chars1[i] - chars2[i];
            }
        }
        return o1.length() - o2.length();
    }
}