題目描述：
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。
輸入描述:
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。
分析：
重點在：全排列和按照字典序
思路：把需要全排列的字符串分為兩部分：
- 字符串的第一個字符
- 第一個字符后面的所有字符（待全排列字符）
為了得到所有可能在第一個位置的字符纲岭，我們將第一個字符依次和后面的字符進行一次交換；交換完成后，固定第一個字符谭梗，對后面的所有字符求全排列，顯然后面的所有字符也可以如上的分為兩個部分宛蚓。
顯然激捏，遞歸可解。
那么凄吏，在這種方法下如何保證“按照字典序”呢远舅？
我們需要知道，ArrayList實現(xiàn)了Collection接口痕钢，實現(xiàn)了sort()方法图柏，其中String類型可以直接使用sort()來實現(xiàn)默認的正序排序。
- 對于String或Integer這些已經實現(xiàn)Comparable接口的類來說任连，可以直接使用Collections.sort方法傳入list參數來實現(xiàn)默認方式（正序）排序蚤吹；
- 如果不想使用默認方式（正序）排序，可以通過Collections.sort傳入第二個參數類型為Comparator來自定義排序規(guī)則课梳；
- 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;
}
}
運行成功
