字符串的排列（java）

题目描述：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

分析：

重点在：全排列和按照字典序

思路：把需要全排列的字符串分为两部分：

• 字符串的第一个字符
• 第一个字符后面的所有字符（待全排列字符）

为了得到所有可能在第一个位置的字符，我们将第一个字符依次和后面的字符进行一次交换；交换完成后，固定第一个字符，对后面的所有字符求全排列，显然后面的所有字符也可以如上的分为两个部分。

显然，递归可解。

那么，在这种方法下如何保证“按照字典序”呢？
我们需要知道，ArrayList实现了Collection接口，实现了sort()方法，其中String类型可以直接使用sort()来实现默认的正序排序。

1. 对于String或Integer这些已经实现Comparable接口的类来说，可以直接使用Collections.sort方法传入list参数来实现默认方式（正序）排序；
2. 如果不想使用默认方式（正序）排序，可以通过Collections.sort传入第二个参数类型为Comparator来自定义排序规则；
3. jdk1.8的Comparator接口有很多新增方法，其中有个reversed()方法比较实用，是用来切换正序和逆序的;

解答：

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public ArrayList<String> Permutation(String str) {
       if (str == null) return null;
        //把字符串转化为数组
        char[] ins = str.toCharArray();
        ArrayList<String> list = new ArrayList<>();
        DoPermutation(ins, 0, list);
        //按字典排序
        Collections.sort(list);
        return list;
    }

    private static void DoPermutation(char[] ins, int i, ArrayList<String> list) {
        if (ins == null) return;
        //如果i指向了最后一个字符
        if (i == ins.length - 1) {
            if (list.contains(String.valueOf(ins))) {
                return;
            }
            list.add(String.valueOf(ins));
        }
        //当i不指向最后一个时，i代表我们做排列操作的字符串的第一个字符
        else {
            for(int j=i;j<ins.length;j++) {
                swap(ins, i, j);//将第一个字符与后面的字符交换
                DoPermutation(ins, i + 1, list); //对后面的字符进行全排列
                swap(ins, j, i);//再将之前交换的字符交换回来，以便于第一个字符再与其他字符进行交换
            }
        }
    }

    /*交换*/
    private static void swap(char[] ins, int i, int j) {
        char tmp = ins[i];
        ins[i] = ins[j];
        ins[j] = tmp;
    }
}

运行成功