題目描述：

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

輸入描述:
輸入一個字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。

分析：

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

思路：把需要全排列的字符串分為兩部分：

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

為了得到所有可能在第一個位置的字符，我們將第一個字符依次和后面的字符進行一次交換；交換完成后，固定第一個字符，對后面的所有字符求全排列，顯然后面的所有字符也可以如上的分為兩個部分。

顯然，遞歸可解。

那么，在這種方法下如何保證“按照字典序”呢？
我們需要知道，ArrayList實現(xiàn)了Collection接口，實現(xiàn)了sort()方法，其中String類型可以直接使用sort()來實現(xiàn)默認的正序排序。

1. 對于String或Integer這些已經(jīng)實現(xiàn)Comparable接口的類來說，可以直接使用Collections.sort方法傳入list參數(shù)來實現(xiàn)默認方式（正序）排序；
2. 如果不想使用默認方式（正序）排序，可以通過Collections.sort傳入第二個參數(shù)類型為Comparator來自定義排序規(guī)則；
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;
        //把字符串轉(zhuǎn)化為數(shù)組
        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));
        }
        //當(dāng)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;
    }
}

運行成功