题目描述：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
分析：
重点在：全排列和按照字典序
思路：把需要全排列的字符串分为两部分：
- 字符串的第一个字符
- 第一个字符后面的所有字符（待全排列字符）
为了得到所有可能在第一个位置的字符，我们将第一个字符依次和后面的字符进行一次交换；交换完成后，固定第一个字符，对后面的所有字符求全排列，显然后面的所有字符也可以如上的分为两个部分。
显然，递归可解。
那么，在这种方法下如何保证“按照字典序”呢？
我们需要知道，ArrayList实现了Collection接口，实现了sort()方法，其中String类型可以直接使用sort()来实现默认的正序排序。
- 对于String或Integer这些已经实现Comparable接口的类来说，可以直接使用Collections.sort方法传入list参数来实现默认方式（正序）排序；
- 如果不想使用默认方式（正序）排序，可以通过Collections.sort传入第二个参数类型为Comparator来自定义排序规则；
- 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;
}
}
运行成功
